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
- Find the waste. The string detour converts bits to characters and back. Shifts can move the bits directly.
- Take the last bit of n.
n & 1is n's lowest bit.n >>= 1drops it, so the next bit becomes the lowest. - Append it to out.
out << 1moves everything inoutone place left, making room;| (n & 1)drops the new bit into the empty lowest place. - Repeat exactly
widthtimes. The first bit taken from n is pushed leftwidth − 1more times, ending in the top position. Running a fixed number of times, notwhile n, is what keeps the leading zeros: after n runs out, the loop still shiftsoutleft.
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 outIn 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
| Approach | Time | Space |
|---|---|---|
| Brute force (string reverse) | O(width): format, reverse and parse width characters | O(width): the string |
| Shift loop (shown code) | O(width): one step per bit, 32 on LeetCode | O(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, soreverse_bits(13, 8)is 176, whilereverse_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 ofwidthtimes: n's leading zeros are never moved across, sooutis not shifted far enough (13 in 8 bits gives 11). - Shifting
outafter 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
nbefore reading its lowest bit, which skips the first bit.
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.
1. A device sends 16-bit sensor words with the bit order swapped. You must restore each word. Which approach fits best?
Bit order must be reversed across the full fixed width, so loop exactly 16 times (or pad the string to 16). Stopping when n reaches 0, or dropping the padding, loses the zeros at the ends.
2. Why does the shown loop run a fixed width times instead of while n?
If n has leading zeros, while n stops early and out is not shifted far enough, so its bits sit too low. For example, 13 in 8 bits would give 11 instead of 176.
3. A learner writes out = (out | (n & 1)) << 1 in the loop. What does reverse_bits(13, 8) now return?
The bit is inserted and then shifted, so after the last step there is one extra shift: 2 × 176 = 352, which no longer fits in 8 bits. Shift first, then insert.
Score 60% or more and the lesson is marked complete.