## 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;