Reverse Bits
Peel off the low bit, push it onto the high end
You never need to compute a destination index. n AND 1 hands you the lowest remaining bit, and result * 2 + bit pushes that bit onto the low end of the answer — so the FIRST bit taken gets shoved left once by every bit that follows it, landing at the far end. Taking bits low-to-high while writing them low-to-high is exactly what reverses the word.
Details
Animated on: n = 43 (binary 00101011) — reverse the order of its bits. Shown over 8 bits so the whole word fits on screen; LeetCode asks for 32, with the identical loop.
Problem:Reverse BitsEasy
Pattern:Bit Manipulation
Peel off the low bit, push it onto the high end
step 1 / 10
n = 43 is 00101011 across 8 bits. Reversing means the bit at position i (counting from the right) has to end up at position 7-i — every bit mirrors across the middle.
1FUNCTION reverseBits(n, WIDTH):2 result <- 03 FOR i <- 0 TO WIDTH - 1:4 bit <- n AND 15 result <- result * 2 + bit6 SHIFT n RIGHT BY 17 RETURN result
← / → step · space play · Home restart
Every step in words
Show all 10 steps
- n = 43 is 00101011 across 8 bits. Reversing means the bit at position i (counting from the right) has to end up at position 7-i — every bit mirrors across the middle.
- n AND 1 pulls off the lowest remaining bit: 1. It sat at position 0 from the right, so the reversal has to land it at position 7 — and pushing it onto the low end of result does exactly that, because the 7 bits still to come will each shove it one more place left. result = 00000001.
- n AND 1 pulls off the lowest remaining bit: 1. It sat at position 1 from the right, so the reversal has to land it at position 6 — and pushing it onto the low end of result does exactly that, because the 6 bits still to come will each shove it one more place left. result = 00000011.
- n AND 1 pulls off the lowest remaining bit: 0. It sat at position 2 from the right, so the reversal has to land it at position 5 — and pushing it onto the low end of result does exactly that, because the 5 bits still to come will each shove it one more place left. result = 00000110.
- n AND 1 pulls off the lowest remaining bit: 1. It sat at position 3 from the right, so the reversal has to land it at position 4 — and pushing it onto the low end of result does exactly that, because the 4 bits still to come will each shove it one more place left. result = 00001101.
- n AND 1 pulls off the lowest remaining bit: 0. It sat at position 4 from the right, so the reversal has to land it at position 3 — and pushing it onto the low end of result does exactly that, because the 3 bits still to come will each shove it one more place left. result = 00011010.
- n AND 1 pulls off the lowest remaining bit: 1. It sat at position 5 from the right, so the reversal has to land it at position 2 — and pushing it onto the low end of result does exactly that, because the 2 bits still to come will each shove it one more place left. result = 00110101. n is now 0, but the loop is NOT done: 2 of n's leading zeros are still real bits that have to be reversed into the low end of result. This is why the loop counts to WIDTH instead of running while n is nonzero.
- n AND 1 pulls off the lowest remaining bit: 0. It sat at position 6 from the right, so the reversal has to land it at position 1 — and pushing it onto the low end of result does exactly that, because the 1 bit still to come will shove it one more place left. result = 01101010.
- n AND 1 pulls off the lowest remaining bit: 0. It sat at position 7 from the right, so the reversal has to land it at position 0 — and pushing it onto the low end of result does exactly that, because this is the last bit taken, so nothing follows to move it again. result = 11010100.
- i has reached 8, so every bit position has been moved exactly once and the loop ends. 00101011 (43) read backwards is 11010100 = 212.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.