LeetCode #190 Easy

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.

bit-manipulation

Open on LeetCode ↗

02

Intuition

The tempting shortcut is to stop the loop once n hits zero, since there is nothing left to shift out. That is wrong: the leading zeros of the input are the trailing zeros of the output, and if you quit early the result never gets shifted into its final position. The loop has to run exactly 32 times no matter what n looks like. Each round takes the lowest bit of n, ORs it onto the bottom of a growing result after shifting that result left one place, then drops the lowest bit of n by shifting it right. Doing this the full 32 times guarantees every position, including the ones that were already zero, ends up where it belongs.

How to spot this pattern

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.

03

Approach

1

Loop exactly 32 times

Do not use a while condition tied to n being nonzero. Use a fixed range of 32 iterations, since a 32-bit integer always has 32 positions to place, even if most of them are zero.

2

Peel the lowest bit of n into result

On each iteration, shift result left by one to make room, then OR in n & 1, the current lowest bit of n. This builds the result from the bottom up, one bit per iteration, in reversed order relative to n.

3

Shift n right to expose the next bit

After extracting the lowest bit, shift n right by one so the next iteration sees the next bit. After 32 iterations every original bit position has been read once and placed into the mirrored position of result.

04

Solution & live demo

▶1class Solution:
▶2    def reverseBits(self, n: int) -> int:
▶3        result = 0
▶4        for _ in range(32):
▶5            bit = n & 1
▶6            result = (result << 1) | bit
▶7            n >>= 1
▶8        return result

05

Common pitfalls

Stopping when n becomes zero

✗ Wrong

while n:
    result = (result << 1) | (n & 1)
    n >>= 1

✓ Right

for _ 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

✗ Wrong

result = (result >> 1) | bit

✓ Right

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

✗ Wrong

n >>= 1;

✓ Right

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.

06

Edge cases

n = 0

Every bit read is 0, so the loop still runs 32 times and correctly returns 0.

n has trailing zero bits at the top (leading in the reversed sense)

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.

n with the sign bit set (as an unsigned 32-bit value)

Treat n as unsigned throughout; in languages with signed shifts, mask with 0xFFFFFFFF after each left shift to avoid sign extension.

n = 0xFFFFFFFF (all bits set)

Result is also 0xFFFFFFFF since the bit pattern is a palindrome; the loop still runs the full 32 rounds.

07

Complexity

Time

O(1) -- always exactly 32 iterations

Space

O(1)

undefined