menu

Friday, November 7, 2014

Using Bitwise and Bitshift Operators In Java

Introduction:

     Today I want to talk about less commonly used and known operators that can be used on integral numbers in Java, Bitwise and Bitshift operators.Bitwise operators most commonly used in masking operations and bitshift operators may be used in encyription or hashing algorithms.I'll try to explain them with some small examples.

Bitwise Operators:

&(Bitwise and) operator: Used to accomplish "and" operation bit by bit.

Example:
int a = 2; //00000000000000000000000000000010 ->32 bit signed(leftmost bit for sign)
int b = 7: //00000000000000000000000000000111 ->32 bit signed(leftmost bit for sign)
int result = a & b;//00000000000000000000000000000010
System.out.println("a & b = " +  result ); // prints 2

Note: All the primitive types are signed in Java.Therefore the max value of an int in java is max 2^31 -1 and min - 2^31.That's because the leftmost bit is used for sign and zero is count in positive numbers that is 0000..0000 is used for zero.
    
(Bitwise inclusive or)  operator: Used to accomplish "inclusive or" operation bit by bit.

Example: 
int a = 2; //00000000000000000000000000000010 ->32 bit signed(leftmost bit for sign)
int b = 7: //00000000000000000000000000000111 ->32 bit signed(leftmost bit for sign)
int result = a | b;//00000000000000000000000000000111
System.out.println("a | b = " +  result); // prints 7

^(Bitwise exclusive or)  operator: Used to accomplish "exclusive or" operation bit by bit.

Example:
int a = 2; //00000000000000000000000000000010 ->32 bit signed(leftmost bit for sign)
int b = 7: //00000000000000000000000000000111 ->32 bit signed(leftmost bit for sign)
int result = a ^ b;//00000000000000000000000000000101
System.out.println("a ^ b = " + result ); // prints 5

 ~(Bitwise negate)  operator: Used to accomplish "negate" operation bit by bit.

 Example: 
int a = 2; //00000000000000000000000000000010 ->32 bit signed(leftmost bit for sign)
int b = 7: //00000000000000000000000000000111 ->32 bit signed(leftmost bit for sign)
int result = ~a;//11111111111111111111111111111101 (negative since the leftmost is 1)
System.out.println("~a = " + result ); // prints negative 3
*The result is the 2's complement of three that is negative 3.
result = ~b;//11111111111111111111111111111000 (negative since the leftmost is 1)
System.out.println("~b = " + result ); // prints negative 8
*The result is the 2's complement of eight that is negative 8.

2's Complement Form:The computers use 2's complement form for the negative values so that the mathematical operations made easily like adding 2 + (-2) instead of subtracting.As an example lets obtain the 2's complement for 3 to get the form of -3 used in computer systems.

1.) 3 = 00000000000000000000000000000011
2.) change 1->0 and 0->1 and get 11111111111111111111111111111100
3.) add 1 and get 11111111111111111111111111111101

As you can see, the result in the step 3 is the representation of -3 which we printed out in the previous example as the result of ~a.

Bitshift Operators:

>>(Bitwise signed right shift)  and <<(Bitwise signed left shift operators: Used to shift a bit pattern to left or right by the given number. If the number is negative the signed shift operator will complete the number with 1 instead 0.

Example:
int a = 2; //00000000000000000000000000000010 ->32 bit signed(leftmost bit for sign)
int b = 7: //00000000000000000000000000000111 ->32 bit signed(leftmost bit for sign)
int c = -7: //11111111111111111111111111111001 ->32 bit signed(leftmost bit for sign)
int result = a << 2;//00000000000000000000000000001000
System.out.println("a << 2 = " + result ); // prints 8
result = b >> 2;//00000000000000000000000000000001
System.out.println("b >> 2 = " + result ); // prints 1
result = c >> 2;//11111111111111111111111111111110

System.out.println("c >> 2 = " + result ); // prints -2

>>>(Bitwise unsigned right shift) operator: Used to shift zero into the leftmost position by the given number even if the number is negative. (unlike signed shift operator)

Example:
int a = 2; //00000000000000000000000000000010 ->32 bit signed(leftmost bit for sign)
int b = 7: //00000000000000000000000000000111 ->32 bit signed(leftmost bit for sign)
int c = -7: //11111111111111111111111111111001 ->32 bit signed(leftmost bit for sign)
int result = a >>> 1;//00000000000000000000000000000001
System.out.println("a >>> 1 = " + result ); // prints 1
result = b >>> 1;//00000000000000000000000000000011
System.out.println("b >>> 1 = " + result ); // prints 3
result = c >>> 2;//00111111111111111111111111111110 (in 2s complement form)

System.out.println("c >>> 2 = " + result ); // prints 1073741822

An Example:

Say we want to count the number of ones in a number. To do that we need to find a way to correctly extract the information from each bit of a number. We can accomplish this by using a mask. For example if you mask each bit with 1 using bitwise and operator, only the bits with value 1 will return 1 and other will return zero. We can use the below method which compare the least significant bit in number by 1 and shift the number to right by 1. Note that this is an unsigned shift.

  int getNumberOfOnesInNumber(int num) {
                int countOnes = 0;
                while (num !=  0) {
                    if ((num & 1 ) == 1) { //compare the LSB with 1
                       countOnes ++;
                     }
                    num = num>>> 1;
                    }
                return countOnes ;
        }


Real World Examples:

1.) Compare roles:

     When you need masking you can use & operator like below.

Example: suppose in a byte the right most bit shows whether it's an admin or not.
byte admin = 1;//00000001
byte role1 = 1;//00000001 --> admin
byte role2 = 2;//00000010 --> not admin
byte role3 = 3;//00000011  --> admin
byte readRoleFromDatabase = 3;//say we read 3 from the database for the user's role.
If you need to understand whether a user in the database is in role admin you can use "bitwise and";
         if ((readRoleFromDatabase  & admin ) > 0) {
            System.out.println("admin");
         }

2.) Check Odd or Even:

      You can use "bitwise and" operator to understand a value is odd or even like below.

Example: 
byte oddVal = 3;//00000011
byte evenVal = 6;//00000110
byte compareVal = 1;//00000001
         if ((oddVal compareVal) > 0)  {
              System.out.println(oddVal  + "is and odd value");
          }
         if ((evenVal compareVal) == 0)  {
               System.out.println(evenVal  + " is an even value");
          }

Note: In the real world examples we use byte variables and shows 8 bits for them in the command lines.However in the real world the computers use 4 bytes even for the byte variables because of the memory model of the 32 bits computers.If we really want to use 1 byte for a byte variable we have to use a byte array.Since the byte array itself uses 4 bytes for its memory representation, the byte values in it need not has to have 4 bytes instead they has 1 byte for each variable.

Conclusion:

     I tried to summarize the usage of the Bitwise and Bitshift operators in Java.As I said, they can be used for masking or in encyription algorithms and they have limited usage in Java.You may use "bitwise and" operator for comparing values or checking if it is odd or even, and may use bitshift operators mostly in encyription or hashing algorithms.


No comments:

Post a Comment