Reverse Bits
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Reverse the bits of a 32-bit unsigned integer.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1How do you read the last bit of n? How do you remove it?
- Hint 2How do you append a bit to the end of the result?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Reading a ticket number backwards: take the last digit off the original and put it at the end of a new number, moving earlier digits one place left. After 32 such moves the new number is the original read backwards.
- The obvious way
Convert to a 32-character string, reverse it, convert back: works but heavy.
- The key insight
Repeat 32 times: result = (result shifted left by 1) OR (n AND 1); then n = n shifted right by 1 (an unsigned shift in Java).
- The algorithm
- result = 0.
- Make room: shift result left.
- Copy the last bit of n into result; shift n right.
- After 32 rounds return result.
Watch it run
Examplen = 0011 (pretend only 4 bits to see the idea)
Last bit of n is 1: result becomes 1. n becomes 001.
result = 1
Where people slip
- Use the unsigned shift >>> in Java so a leading 1 does not copy itself.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def reverse_bits(n):
result = 0
for _ in range(32):
result = (result << 1) | (n & 1) # make room, then copy n's last bit
n >>= 1
return resultNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.