Reverse Bits

Problem

Reverse bits of a given 32 bits unsigned integer.

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 below, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

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.

Constraints:

The input must be a binary string of length 32

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

Solution

Approach 1: Bit by Bit

The key insight is to extract each bit from the right and build the result from the left.

Implementation

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for i in range(32):
            # Extract the rightmost bit
            bit = n & 1
            # Shift result left and add the bit
            result = (result << 1) | bit
            # Shift n right to process next bit
            n >>= 1
        return result

Approach 2: With Power Calculation

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for i in range(32):
            # Extract bit at position i from right
            bit = (n >> i) & 1
            # Place it at position (31 - i) from right
            result |= bit << (31 - i)
        return result

Approach 3: Divide and Conquer (Optimized)

class Solution:
    def reverseBits(self, n: int) -> int:
        # Swap every pair of bits
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1)
        # Swap every pair of 2-bit groups
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2)
        # Swap every pair of 4-bit groups
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)
        # Swap every pair of bytes
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)
        # Swap the two 16-bit halves
        n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16)
        return n

Approach 4: With Lookup Table (For Multiple Calls)

class Solution:
    # Cache for reversing 8-bit numbers
    cache = {}

    def reverseByte(self, byte: int) -> int:
        if byte not in self.cache:
            result = 0
            for i in range(8):
                result = (result << 1) | (byte & 1)
                byte >>= 1
            self.cache[byte] = result
        return self.cache[byte]

    def reverseBits(self, n: int) -> int:
        result = 0
        for i in range(4):
            # Extract byte
            byte = n & 0xFF
            # Reverse and place in result
            result = (result << 8) | self.reverseByte(byte)
            # Move to next byte
            n >>= 8
        return result

Complexity Analysis

Bit by Bit:

Time Complexity: O(1), always process 32 bits.
Space Complexity: O(1)

Divide and Conquer:

Time Complexity: O(1), fixed number of operations.
Space Complexity: O(1)

Lookup Table:

Time Complexity: O(1) per call after cache is built
Space Complexity: O(256) for cache

Key Insights

Bit Extraction: Use n & 1 to extract the rightmost bit.
Build Reversed Number: Shift result left and add each extracted bit.
Fixed Iterations: Always process exactly 32 bits regardless of value.
Left Shift and OR: (result << 1) | bit adds bit to the right of result.
Divide and Conquer: Can optimize by reversing groups of bits (pairs, then 4s, then 8s, etc.).
Mask Patterns:
- 0xaaaaaaaa = 10101010… (odd bits)
- 0x55555555 = 01010101… (even bits)
- 0xcccccccc = 11001100… (pairs of bits)
Optimization for Multiple Calls: Cache reversed values for bytes (256 entries) and process 4 bytes at a time.