Saturday 25 July 2015

How to reverse bits in Java

Today, I'm going to explain how we to reverse the bits in Java. When you take any integer value internally which is represented by bits. Take an example:






int i=5;
By default integer is 32 bit operation:
bitwise (int i=5):
0000 0000  0000 0000  0000 0000  0000 0101
When we say reverse the bit
For above example output would be :
O/P: 1010 0000  0000 0000  0000 0000  0000 0000  ==> Left most bit is 1 means number is negative Now We have to take the 2's complement of o/p:
 
Final out put ==>(-)0110 0000  0000 0000  0000 0000 0000 0000==> -1610612736

How to achieve this:
Take the alternative bits like - 1,3,5,7,........31  and perform & operation with given input:
     0000 0000  0000 0000  0000 0000  0000 0101
&  0101 0101  0101 0101  0101 0101  0101 0101
                                                                                   
     0000 0000  0000 0000  0000 0000  0000 0101

left shift Shift with 1 bit
X==> 0000 0000 0000 0000 0000 0000  0000 1010
Now we have to do first 1 unsigned right shift and then perform & operation with alternative 1's

1 bit Right shift :  0000 0000  0000 0000  0000 0000  0000 0010
                       &   0101 0101  0101 0101  0101 0101  0101 0101
                                                                                                         
Y==>                    0000 0000  0000 0000  0000 0000  0000 0000







now
i==> X|Y

X==>  0000 0000 0000 0000  0000 0000  0000 1010
Y==> 0000 0000  0000 0000  0000 0000  0000 0000
                                                                                       
i==>  0000 0000  0000 0000  0000 0000  0000 1010

Now we have have to find again X and Y by masking 2 alternative bits(first step we did by using masking one alternative bit )

X=  0000 0000  0000 0000  0000 0000  0000 1000
Y=  0000 0000  0000 0000  0000 0000  0000 0010
i =   0000 0000  0000 0000  0000 0000  0000 1010

Now we have have to find again X and Y by masking 4 alternative bits:
X= 0000 0000  0000 0000  0000 0000  1010 0000
Y= 0000 0000  0000 0000  0000 0000  0000 0000
                                                                                
i=  0000 0000  0000 0000  0000 0000  1010 0000


Now we have have to find again X and Y by masking 8 alternative bits:
X=  0000 0000  0000 0000  1010 0000  0000 0000
Y=  0000 0000  0000 0000  0000 0000  0000 0000
 i=  0000 0000  0000 0000  1010 0000  0000 0000

 Now we have have to find again X and Y by masking 16  alternative bits:
X= 1010 0000  0000 0000  0000 0000  0000 0000
Y=  0000 0000  0000 0000  0000 0000  0000 0000
 i=  1010 0000  0000 0000  0000 0000  0000 0000

 Note: we can avoid masking  8 bits and 16 bits, we can have single statement, which is little tricky.

Now Left most bit is 1 means number is negative Now We have to take the 2's complement of o/p:
Final out put ==>(-)0110 0000  0000 0000  0000 0000 0000 0000==> -1610612736







Summary : How your reverse function will look like:

 int reverse(int i){
        i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
        i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
        i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;

         i = (i & 0x00ff00ff) << 8 | (i >>> 8) & 0x00ff00ff;
         i = (i & 0x0000ffff) << 16 | (i >>> 16) & 0x0000ffff;
   return i;






No comments:

Post a Comment