We are given a 32-bit unsigned integer and need to reverse all its bits. This means the least significant bit (position 0) becomes the most significant bit (position 31), position 1 becomes position 30, and so on. It is the same idea as reversing a string, but instead of characters, we are swapping bit positions.

We always work with exactly 32 bits, even if the number is small. For example, the number 1 is 00000000000000000000000000000001 in binary. Reversing it gives 10000000000000000000000000000000, which is 2147483648. Leading zeros in the original number become trailing zeros in the result, and vice versa.

Key Constraints:

Intuition

Reversing bits works the same way as reversing a string: read from one end and write to the other. We extract bits from the right side of the input (least significant) and place them into the result from the left side (most significant).

For each of the 32 bit positions, take the last bit of n, shift the result left by one to make room, and add that bit to the result. Then shift n right by one to expose the next bit. Because we shift the result left once per iteration, the first bit we read ends up shifted left 31 times, landing at the most significant position, which is exactly where the original least significant bit belongs.

Algorithm

Example Walkthrough

Code

The bit-by-bit approach runs in O(1) time, so for a single call it is fine. The follow-up asks about the case where the function is called many times, and there each call still performs 32 loop iterations. The next approach reduces the per-call work by precomputing reversals one byte at a time.

Intuition

When the function is called repeatedly, we can precompute the reversal of every possible byte (8-bit value). There are only 256 possible bytes, so the lookup table is small. To reverse 32 bits, split the integer into 4 bytes, look up each byte's reversal, and reassemble them in reverse order.

This trades 256 table entries for fewer per-call operations: 4 lookups and a few shifts instead of 32 loop iterations.

Algorithm

Example Walkthrough

Take n = 43261596, which is 0x02941E9C. The 4 bytes from high to low are 0x02, 0x94, 0x1E, 0x9C. Each cell below holds one byte; the trace reverses each byte through the table and moves it to the mirrored position.

Code

The lookup table speeds up repeated calls, but it requires 256 entries of precomputed data, and the 4 lookups involve memory access that can stall on a cache miss. The next approach reverses all 32 bits using only bitwise operations, with no table and no memory access.

Intuition

This approach uses divide and conquer. To reverse 32 bits, first swap the left 16 bits with the right 16 bits. Then within each 16-bit half, swap the left 8 bits with the right 8 bits. Continue halving: swap 4-bit nibbles, then 2-bit pairs, then individual adjacent bits. After log2(32) = 5 swaps, every bit has moved to its reversed position.

It is the same idea as reversing a deck of cards by cutting it in half and swapping the halves, then repeating within each half, rather than moving cards one at a time.

Each step uses a bitmask to isolate the bits that move and shifts to put them in their new positions.

How the masks work:

The code applies the swaps from coarsest to finest, halving the block size each step. The two halves of every block are isolated with a mask, shifted in opposite directions, and combined:

Algorithm

Example Walkthrough

Take n = 43261596 = 0x02941E9C again, so the result can be compared against the other approaches. Each cell below holds one byte of the running value; the highlighted cells are the ones the current swap changes.

Code