Reverse Bits

Difficulty: Easy | Acceptance: 68.30% | Paid: No Topics: Divide and Conquer, Bit Manipulation

Reverse bits of a given 32 bits unsigned integer.

Table of Contents

• Examples
• Constraints
• Bit by Bit Iteration
• Divide and Conquer (Bit Swapping)
• Divide and Conquer (Memoization)

Examples

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

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

Constraints

- 0 <= n <= 2^31 - 2
- n is even.

Bit by Bit Iteration

Intuition We can reverse the bits by iterating through each of the 32 bits of the input number. In each step, we extract the least significant bit (LSB) of the input and append it to the result.

Steps

• Initialize result to 0.
• Loop 32 times (once for each bit).
• In each iteration:
  • Left shift result by 1 to make space for the new bit.
  • Get the LSB of n using n & 1.
  • Add this bit to result using bitwise OR |.
  • Right shift n by 1 to process the next bit.
• Return result.

class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0
        for _ in range(32):
            res = (res << 1) | (n & 1)
            n >>= 1
        return res

Complexity

• Time: O(1) - We perform a constant number of operations (32 iterations).
• Space: O(1) - We only use a few variables for storage.
• Notes: This is the most straightforward approach and works well for 32-bit integers.

Divide and Conquer (Bit Swapping)

Intuition We can treat the 32-bit integer as a sequence of bits and swap adjacent bits recursively. First, swap odd and even bits, then swap adjacent pairs of bits, then nibbles (4 bits), then bytes (8 bits), and finally the two 16-bit halves.

Steps

• Mask odd bits with 0x55555555 (0101…) and shift left.
• Mask even bits with 0xAAAAAAAA (1010…) and shift right.
• Combine them.
• Repeat the process for masks 0x33333333/0xCCCCCCCC (2-bit chunks), 0x0F0F0F0F/0xF0F0F0F0 (4-bit chunks), 0x00FF00FF/0xFF00FF00 (8-bit chunks), and 0x0000FFFF/0xFFFF0000 (16-bit chunks).

class Solution:
    def reverseBits(self, n: int) -> int:
        n = (n >> 16) | (n << 16)
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2)
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1)
        return n & 0xffffffff

Complexity

• Time: O(1) - Fixed number of bitwise operations.
• Space: O(1) - No extra space used.
• Notes: This is often faster in practice as it avoids loop overhead and branch prediction, utilizing CPU parallelism for bitwise operations.

Divide and Conquer (Memoization)

Intuition Since a 32-bit integer consists of 4 bytes, and there are only 256 possible values for a byte, we can precompute the reversed bits for all 256 possible bytes. Then, we reverse the 32-bit integer by reversing each byte individually and placing them in the correct positions.

Steps

• Create a cache (array/map) of size 256 to store the reversed bits for values 0 to 255.
• Extract the 4 bytes from the input integer n.
• Look up the reversed value for each byte in the cache.
• Combine the reversed bytes in reverse order (byte 0 becomes the most significant byte, etc.).

class Solution:
    def reverseBits(self, n: int) -> int:
        # Precompute reversed byte values
        cache = {}
        for i in range(256):
            cache[i] = (i >> 7 & 1) << 0 | (i >> 6 & 1) << 1 | \
                       (i >> 5 & 1) << 2 | (i >> 4 & 1) << 3 | \
                       (i >> 3 & 1) << 4 | (i >> 2 & 1) << 5 | \
                       (i >> 1 & 1) << 6 | (i >> 0 & 1) << 7
        
        b0 = (n >> 24) & 0xff
        b1 = (n >> 16) & 0xff
        b2 = (n >> 8) & 0xff
        b3 = (n >> 0) & 0xff
        
        return (cache[b0] << 0) | (cache[b1] << 8) | (cache[b2] << 16) | (cache[b3] << 24)

Complexity

• Time: O(1) - Constant time lookup and combination.
• Space: O(1) - Fixed size cache of 256 integers.
• Notes: This approach is extremely efficient if the function is called multiple times, as the cache is initialized only once.