Reverse Bits

Concept

LeetCode #190.
Problem: Reverse the bits of a given 32 bits unsigned integer.

Input: n = 00000010100101000001111010011100
Output: 00111001011110000010100101000000
(The entire sequence is mirrored backwards).

This problem tests your fundamental mechanical mastery of Bitwise Operators. You must extract a bit from one number, and push it into the exact opposite side of a new number.

The Strategy

1. Create a result variable initialized to 0.
2. Loop 32 times (since it’s a fixed 32-bit integer).
3. Extract: Grab the right-most bit of n using bit = n & 1.
4. Prepare Result: Shift the result to the left by 1 (result = result << 1) to create an empty slot on its right edge.
5. Insert: Drop the extracted bit into that empty slot using OR (result = result | bit).
6. Shift Source: Shift n to the right by 1 (n = n >>> 1) to expose the next bit for extraction on the next loop iteration.

Implementation

// Time Complexity: O(1) (Always loops exactly 32 times)
// Space Complexity: O(1)

function reverseBits(n: number): number {
    let result = 0;

    for (let i = 0; i < 32; i++) {
        // 1. Grab the absolute right-most bit of 'n'
        const bit = n & 1;

        // 2. Shift our result to the left to make physical room for the new bit
        // We do this BEFORE inserting, so the very first bit doesn't get incorrectly shifted!
        // We MUST use logical shift <<
        result = result << 1;

        // 3. Drop the bit into the newly opened slot on the right
        result = result | bit;

        // 4. Shift 'n' to the right to queue up the next bit!
        // We MUST use >>> (Zero-fill right shift) because JavaScript treats bits 
        // as signed integers, and >> would replicate the negative sign bit infinitely!
        n = n >>> 1;
    }

    // 5. In JS, bitwise operations return SIGNED 32-bit integers.
    // The problem explicitly asks for an UNSIGNED integer. 
    // We force JavaScript to cast it back to Unsigned using >>> 0!
    return result >>> 0;
}

The JavaScript Unsigned Trap

Look at the final return statement: return result >>> 0;

This is a bizarre, JavaScript-exclusive hack that FAANG interviewers absolutely love to grill candidates on.
In JavaScript, all numbers are 64-bit Floats. However, the exact millisecond you use a bitwise operator (<<, |, &), JS violently forces the number into a 32-bit SIGNED Integer.

If the reversed binary happens to start with a 1 on the absolute left edge (1011...), JavaScript reads that 1 as a Sign Bit and interprets the final result as a massive negative number (e.g., -123456789). LeetCode will mark this as a catastrophic failure because it expects a massive positive number (e.g., 3,211,000,000).

How do you convert a 32-bit Signed Negative Integer into an Unsigned Positive Integer in JS?
You use the Zero-Fill Right Shift operator by zero positions: >>> 0.
This tells the V8 engine: “Shift the number right by zero spaces (do absolutely nothing to the physical bits), but apply the Zero-Fill Unsigned logic!” The engine drops the Signed context, reads the exact same binary sequence as a pure Unsigned Positive number, and returns the correct massive integer!

Interview Questions

Q: A developer uses a string to solve this: n.toString(2).split('').reverse().join(''). Why is this bad?
A: Aside from the massive $O(N)$ memory allocations and string conversions, it will mathematically fail the test cases. .toString(2) drops leading zeros! The binary 0000...0001 becomes the string "1". Reversing "1" results in "1". But the true answer requires those leading zeros to be mirrored to the back, becoming 1000...0000 (2.14 Billion). To fix the string method, the developer would have to write .padStart(32, '0') which adds even more memory overhead. Bit manipulation solves it flawlessly in pure hardware.