190. Reverse Bits

1. Description

Reverse bits of a given 32 bits unsigned integer.

2. Note

• Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
• In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

3. Follow Up

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

4. Example

Example 1:
Input: n = 00000010100101000001111010011100
Output: 964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:
Input: n = 11111111111111111111111111111101
Output: 3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

5. Constraints

• The input must be a binary string of length 32

6. Solutions

My Accepted Solution

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

// int has 4 bytes, and every byte has 8 bits, so int has 32 bits

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t reversed_n = n;
        reversed_n = (reversed_n >> 1) & M1 | (reversed_n & M1) << 1;
        reversed_n = (reversed_n >> 2) & M2 | (reversed_n & M2) << 2;
        reversed_n = (reversed_n >> 4) & M4 | (reversed_n & M4) << 4;
        reversed_n = (reversed_n >> 8) & M8 | (reversed_n & M8) << 8;

        return reversed_n >> 16 | reversed_n << 16;
    }

private:
    const uint32_t M1 = 0x55555555; // 01010101010101010101010101010101
    const uint32_t M2 = 0x33333333; // 00110011001100110011001100110011
    const uint32_t M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
    const uint32_t M8 = 0x00ff00ff; // 00000000111111110000000011111111
};