Let's explore how to reverse the bits of a 32-bit unsigned integer.

Naive Solution

A straightforward approach is to iterate through the 32 bits, swapping the bits from the start and end towards the middle. This involves extracting each bit and placing it at the opposite end.

def reverse_bits_naive(n):
    result = 0
    for i in range(32):
        if (n >> i) & 1:
            result |= 1 << (31 - i)
    return result

Explanation:

1. We initialize result to 0.
2. We loop from i = 0 to 31.
3. For each i, we check if the i-th bit of n is set.
4. If it is, we set the (31 - i)-th bit of result.
5. Finally, we return result.

• Time Complexity: O(32) = O(1), since the loop runs a fixed 32 times.
• Space Complexity: O(1), as we only use a constant amount of extra space.

Optimal Solution: Bit Manipulation

A more efficient method involves using bit manipulation techniques to reverse the bits. This approach minimizes the number of operations required.

def reverse_bits_optimal(n):
    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

Explanation:

1. We start by swapping the first 16 bits with the last 16 bits.
2. Then, we swap pairs of 8 bits in each 16-bit segment.
3. Next, we swap pairs of 4 bits in each 8-bit segment.
4. We continue swapping pairs of 2 bits and then adjacent bits.
5. This series of swaps efficiently reverses the entire 32-bit integer.

• Time Complexity: O(1), as it involves a fixed number of bitwise operations.
• Space Complexity: O(1), since we only use a constant amount of extra space.

Edge Cases

• Zero Input: If the input is 0, the reversed output will also be 0. Both solutions handle this correctly.
• All Ones Input: If the input consists of all ones, the reversed output will also be all ones. Both solutions correctly handle this.

Optimization via Caching (Follow-up Question)

If this function is called many times, we can optimize it using a lookup table (cache). We can precompute the reversed values for all possible 8-bit integers (0-255) and store them in a cache. Then, for any 32-bit integer, we can split it into four 8-bit chunks, look up the reversed value for each chunk in the cache, and combine the reversed chunks to form the final reversed integer.

class Solution:
    def __init__(self):
        self.cache = {}

    def reverse_bits_cached(self, n):
        result = 0
        for i in range(4):
            byte = (n >> (i * 8)) & 0xFF
            reversed_byte = self.reverse_byte(byte)
            result |= reversed_byte << ((3 - i) * 8)
        return result

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

Explanation:

1. We create a cache to store the reversed values of 8-bit integers.
2. We split the 32-bit integer into four 8-bit chunks.
3. For each chunk, we look up the reversed value in the cache. If it's not in the cache, we compute it and store it.
4. We combine the reversed chunks to form the final reversed integer.

• Time Complexity: O(1) amortized, as the cache lookups are O(1) and the reverse byte calculation is only done once for each byte.
• Space Complexity: O(256), as the cache stores the reversed values for all 256 possible 8-bit integers.