Bit Manipulation in Java

Java inherited bit manipulation from C. As a programmer you might not use it often, but still, it's quite important. Java integers are of 32 bits (4 bytes) and are signed. This means that left most bit (Most Significant Bit / MSB) works as the sign identifier. If it's 1, the number is negative (and positive if it's 0). Let's go in detail on the binary form of numbers:

Binary Representation of Numbers

Integer 1 in binary form  = 00000000000000000000000000000001  or 1

Integer -1 in binary form =11111111111111111111111111111111

In Java, you can get the binary representation of any number by calling toBinaryString() method of Integer class (Integer.toBinaryString(1)). The binary representation of -1 might be confusing if you are not aware of how negative numbers gets stored. Negative numbers get stored as two's complement which can be achieved by adding 1 to the NOT of the unsigned number i.e. ~number +1

Another way to look at it is, the weight of the MSB or leftmost bit is negative. So when this bit is 1, the number becomes negative. The binary form of -1 can be represented as:
   -2^31*1+ 2^30*1 + 2^29*1 + 2^28*1+ .... ......+ 2^1*1+2^0*1

Note that, the highest weighted component is negative (-2^31*1). This will result in the overall number being negative. We can cross check it by assuming a 4-bit number system.

1111 = -2^3*1 + 2^2*1 + 2^1*1 + 2^0*1
         = -8 +4 + 2 +1
         = -1

Using two's complement technique, -1 = ~1 +1
       -1 = ~1+1
          =  ~0001 + 1
          =   1110 + 1
          =   1111      

So either way, you will get the same representation of a negative number.

Bitwise Operators

We have used NOT binary operator above, now it's time to go over Java binary operators in detail. 

~ (NOT)
Flips or reverses all bits. Thus, every 1 becomes 0 and every 0 becomes 1. Also known as one's complement operator. It's a urinary operator so takes only one argument.
~101 produces 010

| (OR)
Produces one in output if at least one of the bit is 1 and produces 0 if both bits are 0.
101 | 10 produces 111

& (AND)
Produces 1 in output if both input bits are 1, otherwise, it results in 0.
101 & 10 produces 000

^ (EXCLUSIVE OR / XOR)
Produces 1 in the output if either of the bit is 1 (not both), otherwise 0
101 ^ 10 produces 111
2 ^ 10 produces 8  ( equivalent to 10 ^ 1010 )

Important Note

• Difference between bitwise operators (&, |) with logical operators && and ||. Bit operators take integers and results in other integers but logical operators take booleans and return a boolean result.
• Only NOT (~) is urinary, others are binary operators. 
• Binary operators (i.e. | , & and ^) can be combined with the = sign like &=, |= and ^=

Shift Operators

Now let's go to the Java's powerful shift operators. 

<< (Left Shift Operator)

Used for shifting bits of a number on left side (i.e. 8 << 1 or 00001000 << 1). The value to the right of the operator indicates how many positions to shift the bits. Bits that fall off on the left side are lost and empty bits on the right side are filled up with 0. 

Note, the value can change sign depending on the state of first bit. 

>> (Signed Right Shift Operator)

Used for shifting bits of a number on the right side ( 8 >> 1). The value to the right of the operator indicates how many positions to shift the bits. 

• When the sign is positive (leftmost bit is 0),  empty bits on left side fills up with 0. So it retains the sign. 
• When the sign is negative (leftmost bit is 1), it performs sign extension. Fills up the empty bits on the left side with 1s. 

>>> (Unsigned Right Shift Operator)

Regardless of the sign, zeros are inserted to the left side or higher order bits.

Let's take a simple example to illustrate above operators

 public class BinaryOperators {  
      public static void main(String[] args) {  
           int i = 17;  
           System.out.println(" i :" + Integer.toBinaryString(i));  
           System.out.println(" ~i : " + Integer.toBinaryString(~i));  
           System.out.println(" -1 : " + Integer.toBinaryString(-1));  
           System.out.println(" -1 & i : " + Integer.toBinaryString(-1 & i));  
           System.out.println(" -1 ^ i : " + Integer.toBinaryString(-1 & i));  
           System.out.println(" i >> 2 : " + Integer.toBinaryString(i >> 2));  
           System.out.println(" i >>> 2 : " + Integer.toBinaryString(i >>> 2));  
           System.out.println(" i << 2 : " + Integer.toBinaryString(i << 2));  
           System.out.println(" -1 >> 2 : " + Integer.toBinaryString(-1 >> 2));  
           System.out.println(" -1 >>> 2 : " + Integer.toBinaryString(-1 >>> 2));  
           System.out.println(" -i >>>= 2 : " + Integer.toBinaryString(i >>>= 2));  
      }  
 }  

Output:
 i :10001
 ~i : 11111111111111111111111111101110
 -1 : 11111111111111111111111111111111
 -1 & i : 10001
 -1 ^ i : 10001
 i >> 2 : 100
 i >>> 2 : 100
 i << 2 : 1000100
 -1 >> 2 : 11111111111111111111111111111111
 -1 >>> 2 : 111111111111111111111111111111
 -i >>>= 2 : 100

Important Observations: 

• Multiplication and Division:

      Shift operators can be used to multiply or divide a number. So if there is a need to multiply or divide a number by multiple of 2; you should prefer shift operators as it's more efficient. 

          int i = 5;

          i <<= 2 ;    //value of i becomes 20 i.e. 5*2*2

          i = 10;

          i >>=2;   // value of i becomes 2 i.e. 10/(2*2) = 2

          i = -4

          i >>=2 ;   // value of i becomes -1

• Finding bit at a position:

           If you & a bit with 1; you will get the same bit.

           i.e. 0 & 1 = 0 ; 1&1 = 1

           This can be used to get the bit value in a number at the given position. 

           

           5 & 1 = 1   // 1001 & 1 

           5 &  10  = 0 // 1001 & 10; second last bit is 0 so the output is 0

     

References:

http://sol.gfxile.net/boolean.html
http://graphics.stanford.edu/~seander/bithacks.html

----
that's it for now...do post your feedback about this post.