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
3221225472Practice:
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 :
32212254721 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
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);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
