The O(n) Club: Reverse Bits—When Your Integers Stage a Flash Mob
⚡ TL;DR
We’re flipping every bit in a 32-bit number. Take the far right bit, stick it far left, and so on—until everyone’s swapped places and you look like a bitwise wizard.
Here’s how Java does it (in fewer lines than your weekly sprint retro):public int reverseBits(int n) { int res = 0; for (int i = 0; i < 32; i++) { res = (res << 1) | (n & 1); n = n >>> 1; } return res; }
🧠 How Devs Usually Mess This Up
Three ways to embarrass yourself at the algorithm party:
- Unsigned Panic: Java doesn’t have unsigned ints, but the bits still go to the same party. Calm down and use
>>>
(triple shift). - Shifty Moves: Mess up
<<
and>>>
? Your bits go the wrong way and end up crashing someone else’s array. - Zero Ghosting: Don’t ignore leading zeros. They might not RSVP, but they count.
🔍 What’s Actually Going On
Think of your 32-bit integer as a conga line of party guests. You pluck the last dancer, put her first, and repeat until the group’s done the robot in reverse. Each time, you left-shift your result to make room, tack on the newest bit with OR, and unsigned right-shift n to serve up the next guest. No extra data structures, no excuses.
🛠️ PseudoCode
- Start with
int res = 0;
(the empty dance floor) - For 32 times:
- Left shift
res
to make room (res = res << 1
) - Copy the last bit from
n
(n & 1
), add with OR - Unsigned right shift n (
n = n >>> 1
) so the next bit lines up
- Left shift
- Return
res
; you’re done, time for confetti
💻 The Code
public int reverseBits(int n) {
int res = 0;
for (int i = 0; i < 32; i++) {
res = (res << 1) | (n & 1); // add next bit to the left
n = n >>> 1; // unsigned shift heals all Java woes
}
return res;
}
⚠️ Pitfalls, Traps & Runtime Smacks
- Triple Shift or Bust: Java’s
>>>
is your friend—use it or sign bits come to haunt your output. - Don’t Forget the Zeroes: 1000 becomes 000…1. Still 32 bits, even if your feelings say otherwise.
- Speed Freaks: Need to reverse bits millions of times? Get fancy: use lookup tables for groups of 8 bits. For one-offs, keep it simple.
- Complexities: Always 32 steps, always O(1) space. Unless you’re reversing a universe-sized int, you’re good.
🧠 Interviewer Brain-Tattoo
“Reverse bits: because sometimes, your integer just wants to moonwalk for the interviewer.”