Reverse Bits

Reverse bits of an 32 bit unsigned integer

Example 1:

x = 0,

          00000000000000000000000000000000  
=>        00000000000000000000000000000000

return 0

Example 2:

x = 3,

          00000000000000000000000000000011 
=>        11000000000000000000000000000000

return 3221225472

Since java does not have unsigned int, use long

Method:

The important thing to know is how to set a bit.

We do it by

a & ~(1 << index) | (val << index);

 ~(1 << index) will give us a zero mask like 011111, so a & ~(1 << index) will unset the bit at index for number a
then | (val << index) will set the bit at index to val

Solution:

Time: O(1)
Space: O(1)

public class Solution {
    public long reverse(long a) {
        int left = 31;
        int right = 0;
        long result = a;
        while (left > right) {
            long leftVal = (a >> left) & 1;
            long rightVal = (a >> right) & 1;
            result = setBit(result, left, rightVal);
            result = setBit(result, right, leftVal);
            left--;
            right++;
        }
        return result;
    }
    
    private long setBit(long a, int index, long val) {
        return a & ~(1 << index) | (val << index);
    }
}