Reverse Bits

Reverse Bits is the classic bit-manipulation warm-up. It teaches the two operations every bit problem leans on: reading the lowest bit with n & 1, and shifting to move bits around. The whole trick is to drain the input one bit at a time while filling the answer from the bottom up.

The slow way first

You could turn the number into a string of bits, reverse the string, and parse it back. That works, but it allocates a string, depends on padding the bits to the right width, and hides what is actually happening. Interviewers want the arithmetic version: build the answer using only shifts and masks, no strings.

The question to ask: while I peel one bit off the input, where does it belong in the output? The lowest bit of the input must become the highest bit of the output. If I always add new bits to the bottom of the result and keep shifting, the first bit I read ends up pushed all the way to the top — exactly where it belongs.

The idea: drain low, fill low

Loop 8 times. Each pass: grab the bottom bit of n with n & 1. Shift result left by one (this opens an empty slot at its low end and pushes everything already there up by one position). Then OR the grabbed bit into that empty low slot. Finally shift n right by one to throw away the bit you just used.

The key insight: shifting result left before every OR means the first bit you read gets shifted left 7 more times, landing at the top — so reading the input low-to-high writes the output high-to-low. That is the reversal.

Walk through it

Step through the animation. The top row is n; the n&1 pointer marks the bit being read, moving right to left as the input drains. The bottom row is result; the lsb pointer marks where the newest bit lands. Watch the bit you read at the right of the top row reappear, then march toward the left of the bottom row as later shifts push it along.

Pseudocode

result = 0
repeat 8 times:
    bit = the lowest bit of n          # n AND 1
    shift result left by one           # opens an empty low slot
    set that low slot to bit           # result OR bit
    shift n right by one               # discard the bit we just used
return result

The Python solution

def reverse_bits(n):
    result = 0
    for _ in range(8):
        bit = n & 1
        result = result << 1
        result = result | bit
        n = n >> 1
    return result

• result starts at 0 and is built up one bit at a time from its low end.
• bit = n & 1 masks off everything but the lowest bit, giving 0 or 1.
• result = result << 1 shifts the answer left, opening an empty slot at the bottom — this is what eventually pushes early bits to the top.
• result = result | bit drops the freshly read bit into that empty low slot.
• n = n >> 1 discards the bit we just consumed so the next pass reads the next one.

Complexity

The loop count is fixed by the bit width, not the value, so this is constant time and constant space. No strings, no extra arrays — just a handful of shifts and masks.

When this pattern shows up

Practice