The O(n) Club: Reverse Bits—When Your Integers Stage a Flash Mob

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
  • 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.”

Previous Article

The O(n) Club: Fibonacci Number: Attack of the Useless Recursion

Next Article

The O(n) Club: The Shortest Subarray with Sum at Least K (When Negatives Sabotage Everything)