leetcode Questions: Reverse Bits

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

Analysis:

This is a very basic bit manipulation problem.

Some experience about the basic bit operation (not the STL in C++):
1. mask is a very good tool
2. bit shifting operations (<<, >>) are very inportant
3. loop is usually enough
4. be careful with the data type.


In this problem, the first task is to get the binary bits from uint number n.
Let's say n = 43261596,  the binary format is: 00000010100101000001111010011100
In order to get the binary bits, mask is used here.
The idea of using mask to check 1 bit each time, using AND operation.

Mask moves 1 bit each time using << operation.
Mask can be computed and saved before to speed up the reverse function.

E.g.
iteration 1:  mask = 0000...00001,  then mask & n  = 0
iteration 2:  mask = 0000...00010, then mask & n  = 0
iteration 3:  mask = 0000...00100,  then mask & n  = 1
iteration 4:  mask = 0000...01000, then mask & n  = 1
...
iteration 32:  mask = 1000...00000, then mask & n  = 0

In this way, binary bits can be obtained from 32 iterations.
Reverse thus becomes pretty easy when using this looping.


The next step is to convert bits back into integer. Bit shift is all we need. "<< " shifts 1 bit left. (Remember if you shift left on an unsigned int by K bits, this is equivalent to multiplying by 2^K.)
In this problem, we check the original int from the lowest bit to highest, so the first bit in the original int is the highest bit in the result int. By shifting the final int 1 bit each time, the final int after 31 (32-1) times shifting, it becomes the reverse int of the original int.  32 is the length of the int data type in this problem.

Code(C++):

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        uint32_t mask = 1;
        for (int i=0;i<32;i++){
            if (n&mask) res = res + 1;
            if (i!=31) res <<= 1;
            mask <<= 1;
        }
        return res;
    }
};

Code(Python):

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        res = 0
        mask = 1
        for i in range(0,32):
            if n & mask:
                res += 1
            if i != 31:
                res <<= 1
            mask <<= 1
        return res