Reverse Bits
Reverse the 32 bits of an unsigned integer by shifting exactly 32 times regardless of how early the input runs out of set bits.
- 0 <= n <= 2³¹ - 2
- n is even.
Intuition
Reverse bits reverses the order of all 32 bits in an unsigned integer — the bit at position 0 moves to position 31, and so on. The straightforward loop does this one bit at a time: - Shift the result left, OR in the input's lowest bit, then shift the input right — repeat 32 times. Each iteration moves one bit from the input's bottom to the result's bottom while pushing earlier bits leftward, which reverses the order naturally. The loop must run exactly 32 times, not until the input becomes zero. Stopping early on a small input like 1 leaves the result unshifted, so the answer comes out as 1 rather than 2³¹. This is the most common bug in the problem. In Java the result must be built with unsigned semantics, and in Python the value must be masked to 32 bits, since Python integers have no fixed width and would otherwise keep growing. The divide-and-conquer version reverses in five steps instead of 32, using masks to swap progressively larger groups: adjacent bits, then pairs, then nibbles, then bytes, then halves. Each step is a shift-and-mask, and the whole reversal costs five operations. The follow-up asks about calling the function repeatedly. A byte-level lookup table of 256 precomputed reversals answers each call in four lookups and three shifts, trading 256 entries of memory for the speed. All variants are O(1) — the bit width is fixed, so nothing scales with input size.
Shift the result left while shifting the input right, moving one bit across per step. The loop runs a fixed 32 times because the answer is defined over a 32-bit width — stopping when n hits zero would silently drop the leading zeros that must become trailing ones.
Approach
Before reading on: price up what the direct approach costs here, then ask which operator makes the unwanted values cancel themselves out. Aim for O(1) -- always exactly 32 iterations time and O(1) space.
Move one bit per iteration
Shift the result left, OR in the input's lowest bit, shift the input right. Earlier bits are pushed leftward, which reverses the order.
Always run 32 iterations
Loop exactly 32 times, not until the input is zero. Stopping early leaves the result unshifted — input 1 returns 1 instead of 2³¹.
Mind the language's integer width
Java needs unsigned shift semantics; Python needs an explicit 32-bit mask, since its integers have no fixed width and grow indefinitely.
Know the five-step version
Swap adjacent bits, then pairs, nibbles, bytes, and halves using masks. Five shift-and-mask operations replace all 32 iterations.
Answer the follow-up with a table
For repeated calls, precompute all 256 byte reversals and combine four lookups. Trades memory for near-instant answers.
Cost of the approaches
All are O(1) time and space — the 32-bit width is fixed, so nothing scales with the input's value.
Solution & live demo
Common pitfalls
Stopping when n becomes zero
while n:
result = (result << 1) | (n & 1)
n >>= 1for _ in range(32):
High-order zeros in the input are low-order zeros in the output and still need their shifts. Exiting early leaves the result shifted too far right — correct bits, wrong magnitude.
Shifting the result right
result = (result >> 1) | bit
result = (result << 1) | bit
Each new bit must land in the low position while everything already placed moves up. Shifting right discards previously placed bits and leaves only the last one.
Using a signed shift on the input in Java
n >>= 1;
n >>>= 1;
For a negative input the arithmetic shift keeps feeding in 1s, so the reversal fills with garbage. The unsigned shift treats the value as the raw 32-bit pattern the problem describes.
Edge cases
Every bit read is 0, so the loop still runs 32 times and correctly returns 0.
Those zero bits still get shifted into result at the correct low positions during the later iterations, which is exactly why the loop cannot exit early.
Treat n as unsigned throughout; in languages with signed shifts, mask with 0xFFFFFFFF after each left shift to avoid sign extension.
Result is also 0xFFFFFFFF since the bit pattern is a palindrome; the loop still runs the full 32 rounds.