Sunday, March 16, 2014

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 binary representation of any number by calling toBinaryString() method of Integer class (Integer.toBinaryString(1)). 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 left most bit is negative. So when this bit is 1, the number becomes negative. 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 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 ones complement operator. It's an 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 another integers but logical operators take booleans and returns 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 left side are lost and empty bits on right side are filled up with 0 . 
Note, value can change sign depending on the state of new first bit. 

>>(Signed Right Shift Operator)
Used for shifting bits of a number on right side ( 8 >> 1). The value to the right of the operator indicates how many positions to shift the bits. 
  • When sign is positive (left most bit is 0),  empty bits on left side fills up with 0. So it retains the sign. 
  • When sign is negative (left most bit is 1), it performs sign extension. Fills up the empty bits on left side with 1s. 
>>> (Unsigned Right Shift Operator)
Regardless of the sign, zeros are inserted to 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
----
that's it for now...do post your feedback about this post. 

No comments:

Post a Comment