Reverse Bits · DSA Prep

n is treated as a fixed-width 32-bit sequence, and the answer is that sequence read backwards. The direct way is to peel off one bit at a time from the low end of n and place it at the corresponding position from the high end of the result.

Bit by Bit

Time O(32) = O(1)Space O(1)

For each of the 32 positions i, read the bit of n at position i ((n >> i) & 1) and write it into the mirrored position 31 - i of the result.

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

Tracing the low end of n = 43261596 (binary 00000010100101000001111010011100, shown left-to-right as bit 31 down to bit 0):

i=0:  n's bit 0 is 0 -> write 0 to result's bit 31
i=1:  n's bit 1 is 0 -> write 0 to result's bit 30
i=2:  n's bit 2 is 1 -> write 1 to result's bit 29
i=3:  n's bit 3 is 1 -> write 1 to result's bit 28
...   (continues through i=31)
result = 00111001011110000010100101000000 = 964176192

Complexity: always exactly 32 iterations, each doing O(1) shifting and masking → O(1) time (bounded by the fixed 32-bit width), O(1) space.

Byte Lookup Table

OptimalTime O(1) per call after O(1) preprocessingSpace O(1)

The follow-up asks about repeated calls. Reversing bits one at a time redoes the same small amount of work every call. Instead, split the 32-bit input into four 8-bit bytes, reverse each byte using a precomputed 256-entry table (or a fixed constant-time bit-swap trick), and reassemble the bytes in reverse order — byte 0 of n becomes byte 3 of the result, byte 1 becomes byte 2, and so on.

def reverse_byte(b: int) -> int:
    b = (b & 0xF0) >> 4 | (b & 0x0F) << 4  # swap nibbles
    b = (b & 0xCC) >> 2 | (b & 0x33) << 2  # swap pairs of bits
    b = (b & 0xAA) >> 1 | (b & 0x55) << 1  # swap adjacent bits
    return b

class Solution:
    def reverseBits(self, n: int) -> int:
        b0 = n & 0xFF
        b1 = (n >> 8) & 0xFF
        b2 = (n >> 16) & 0xFF
        b3 = (n >> 24) & 0xFF
        return (
            (reverse_byte(b0) << 24)
            | (reverse_byte(b1) << 16)
            | (reverse_byte(b2) << 8)
            | reverse_byte(b3)
        )

reverse_byte reverses a byte with 3 fixed shift-and-mask steps regardless of the byte’s value (swap nibbles, then pairs of bits, then adjacent bits) — no loop needed. For n = 43261596, the four bytes b0..b3 each get reversed independently and reassembled in swapped byte order to produce 964176192, matching the bit-by-bit trace above.

Complexity: every step is a fixed number of O(1) operations independent of n → O(1) time per call, O(1) space. In a real system you would replace reverse_byte with a precomputed 256-entry array (table[b] = reversed byte), built once in O(1) amortized setup, turning each call into four array lookups instead of even the fixed bit-swap arithmetic — this is the concrete answer to “called many times.”