LeetCode 190 · Bit Manipulation

Reverse Bits, explained with a picture

Reading a switch panel in a mirror.

EasyBit Manipulation
▶ Watch it step by step

The problem

Reverse the order of the bits of a number. (LeetCode uses 32 bits; the picture uses 8 so it fits.)

Input:  13 = 00001101 (8 bits)
Output: 176 = 10110000

Picture it

Picture a switch panel held up to a mirror. We read switches from the right end of the original one by one and push each onto the right end of a new panel, shifting the new panel left each time. After all the switches, the new panel is the mirror image.

How to recognise it

  • The number is treated as a fixed-width row of bits (32 on LeetCode, 8 in the picture), and you must reverse that row.
  • Leading zeros matter: 13 in 8 bits is 0000 1101, and its reverse 1011 0000 is 176, not 11 (the reverse of 1101).
  • Reading bits from the right of one number and writing them on the right of another reverses their order, like moving cards from one stack to another.
  • The width is fixed, so every approach is O(width); the point is doing it with shifts.

Start with brute force

Write the number as a zero-padded binary string, reverse the string and read it back.

def reverse_bits_brute(n, width=32):
    return int(format(n, f"0{width}b")[::-1], 2)

This is short and correct for 0 ≤ n < 2^width. It is O(width) like the shown code, so it is not slow. It does build a string, and it depends on padding: without the 0{width} the leading zeros are lost and the answer is wrong. In languages without easy string formatting, the bit loop is the standard tool.

From brute force to the idea

  1. Find the waste. The string detour converts bits to characters and back. Shifts can move the bits directly.
  2. Take the last bit of n. n & 1 is n's lowest bit. n >>= 1 drops it, so the next bit becomes the lowest.
  3. Append it to out. out << 1 moves everything in out one place left, making room; | (n & 1) drops the new bit into the empty lowest place.
  4. Repeat exactly width times. The first bit taken from n is pushed left width − 1 more times, ending in the top position. Running a fixed number of times, not while n, is what keeps the leading zeros: after n runs out, the loop still shifts out left.

This is the key idea: pop bits off the right of n and push them onto the right of out, exactly width times.

The key idea

For each bit: result = (result << 1) | (n & 1); n >>= 1.

Python solution

def reverse_bits(n, width=32):     # this scene uses width = 8
    out = 0
    for _ in range(width):
        out = (out << 1) | (n & 1)   # take n’s last switch
        n >>= 1
    return out

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (string reverse)O(width): format, reverse and parse width charactersO(width): the string
Shift loop (shown code)O(width): one step per bit, 32 on LeetCodeO(1): two integers

Edge cases

  • n = 0: returns 0.
  • n = 1: returns 2^31 = 2147483648 with width 32 (or 128 with width 8).
  • All ones (2^32 − 1): unchanged.
  • Default width: the function defaults to 32, as on LeetCode; the 8-bit picture calls it with width=8, so reverse_bits(13, 8) is 176, while reverse_bits(13) is 2952790016.
  • n wider than width: bits above the width are ignored without warning. reverse_bits(256, 8) returns 0, because 256 needs 9 bits.
  • Negative n: not meaningful here; Python's >> on a negative number keeps the sign. LeetCode's inputs are non-negative.

Common mistakes

  • Looping while n: instead of width times: n's leading zeros are never moved across, so out is not shifted far enough (13 in 8 bits gives 11).
  • Shifting out after inserting the bit instead of before, which doubles the result and pushes it past the width.
  • Reversing bin(n)[2:] without padding, so 13 becomes 11 instead of 176 (8 bits).
  • Shifting n before reading its lowest bit, which skips the first bit.
Your turn: is the bit pattern a palindrome?

Decide whether the width-bit pattern of n reads the same in both directions. With 8 bits, 129 (1000 0001) is a palindrome and 13 (0000 1101) is not. Describe your approach, then write it if you like.

Compare with our answer

A pattern is a palindrome exactly when reversing it gives the same number, so reuse the reversal with the same width.

def is_bit_palindrome(n, width=32):
    return reverse_bits(n, width) == n

Time O(width), space O(1). The width matters: 9 is a palindrome in 4 bits (1001) but not in 8 bits (0000 1001).

A strong answer mentions: comparing the reversal with the original, that the answer depends on the chosen width, and that leading zeros are part of the pattern.

Check what stuck

1. A device sends 16-bit sensor words with the bit order swapped. You must restore each word. Which approach fits best?

2. Why does the shown loop run a fixed width times instead of while n?

3. A learner writes out = (out | (n & 1)) << 1 in the loop. What does reverse_bits(13, 8) now return?

Score 60% or more and the lesson is marked complete.