Reverse Bits

• LeetCode: Reverse Bits

• Problem:

Reverse bits of a given 32 bits unsigned integer.

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

• Follow up:

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

Related problem: Reverse Integer

• Analysis:

Let the input 32 bits unsigned integer is A31 * 2^31 + A30 * 2^30 + .... + A0 * 2^0.

Reverse bits is A0 * 2 ^ 31 + A1 * 2 ^ 30 + .... + A31.

• Code - Java:

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = 2 * result + (n & 1);
            n >>= 1;
        }
        return result;
    }
}

• Code - C++:

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        for (int i = 0; i < 32; i++) {
            result = 2 * result + (n & 1);
            n >>= 1;
        }
        return result;
    }
};

• Code - Python:

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        result = 0
        for i in range(32):
            result = 2 * result + (n & 1)
            n >>= 1
        return result

• Code - C:

uint32_t reverseBits(uint32_t n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result = 2 * result + (n & 1);
        n >>= 1;
    }
    return result;
}