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.

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

python

▶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

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.

06

Complexity

Time

O(1) -- always exactly 32 iterations

Space

O(1)

undefined