Reverse unsigned 32 bit integer - facebook code lab - 5+ practice

July 16, 2016

Problem statement:

REVBITS

Reverse bits of an 32 bit unsigned integer

Example 1:

x = 0,

          00000000000000000000000000000000  
=>        00000000000000000000000000000000

return 0

Example 2:

x = 3,

          00000000000000000000000000000011 
=>        11000000000000000000000000000000

return 3221225472

Practice:

Java Practice:
1st practice: 
code is working, but Java code is using Math.pow(2, index).
https://gist.github.com/jianminchen/395ccf0277250e5d3d68498e0d2238f1

2nd practice: not working, error on 32 bit integer, left most significant bit 1 means negative number. 
https://gist.github.com/jianminchen/7bfdcd0c1643bf01c2bf6ba7acea6f70

Sorry, wrong answer. Your program's output doesn't match the expected output. You can try testing your code with custom input and try putting debug statements in your code.

Your submission failed for the following input:

A : 3

Your function returned the following :

-1073741824

The expected returned value :

3221225472

line 11:  ret += 1 << power;
1 is int with 32 bit.
http://stackoverflow.com/questions/1032982/is-a-java-int-always-32-bits

should be: ret += ((long)1) << power;

3rd practice: fail to fix the issue. 
https://gist.github.com/jianminchen/2b753978ffe983600a031a0fcda7b3a6

4th practice: Use bit manipulation - left shift to get 2^n value - code is working

https://gist.github.com/jianminchen/6a5c1ab71b01414f008b22386000ee59

5th practice:

First, study the solution provided by lab, great idea:

Reversing bits could be done by swapping the n/2 least significant bits with its most significant bits.

The trick is to implement a function called swapBits(i, j), which swaps the ‘i’th bit with the ‘j’th bit.

If you still remember how XOR operation works:

here

0 ^ 0 == 0, 
1 ^ 1 == 0, 
0 ^ 1 == 1, and 
1 ^ 0 == 1.

We only need to perform the swap when the ‘i’th bit and the ‘j’th bit are different.

To test if two bits are different, we could use the XOR operation. Then, we need to toggle both ‘i’th and ‘j’th bits.

We could apply the XOR operation again.

By XOR-ing the ‘i’th and ‘j’th bit with 1, both bits are toggled.

Bonus approach (The divide and conquer approach):

Remember how merge sort works? Let us use an example of n == 8 (one byte) to see how this works:

Remember how merge sort works? Let us use an example of n == 8 (one byte) to see how this works:

              01101001

             /        \

           0110       1001

          /   \       /   \

         01    10    10    01

        /\     /\    /\     /\

       0  1   1  0  1  0   0  1

The first step is to swap all odd and even bits. After that swap consecutive pairs of bits, and so on …

Therefore, only a total of log(n) operations are necessary.

Example:

For the first step, you would do:

    x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);

Julia's comment:  5 minutes workout - how to swap odd bit and even bits?
  5 = 101
How to swap odd bit and even bits?
In other words, odd bit becomes even bit; even bit goes to odd bit

First, odd bit shifts to left; even bit shifts to right.

32 bits: 0101 0101 0101 0101 0101 0101 0101 0101
  all odd bit number in x:
    x & 0x55555555
 left shift 1 bit: 
 (x & 0x55555555) << 1)

So, even bits shift to right; 
  A in bits presentation: 1010 
all even bit number in x:
  x & 0xAAAAAAAA

After the swap, the new value is 
   x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
-- end of Julia's comment --

study the code in C++:
https://gist.github.com/jianminchen/3526dd68e72ae97563cdd61580052016

Fresh from his first grass court final, @milosraonic is thriving under coach McEnroe.#Wimbledonhttps://t.co/AWVQyfUugI

— Wimbledon (@Wimbledon) June 22, 2016