HARD Lab · Binary · 25

190. Reverse Bits

Treat the 32-bit integer as a fixed-width bit string and reverse it: peel the least-significant bit one iteration at a time, shifting it into the result from the left, until all 32 positions are filled.

● EasyBit ManipulationTypeScript

PROBLEM What we're solving

Given a 32-bit unsigned integer, return the integer whose binary representation is the bit-reversal of the input's 32-bit binary representation. n = 43261596 in binary is 00000010100101000001111010011100; reversed it is 00111001011110000010100101000000 = 964176192. Bit 0 (LSB) swaps with bit 31, bit 1 swaps with bit 30, and so on.

KEY IDEA Peel from the right, build from the left

Insight → instead of thinking about swapping pairs, stream bits from the input one at a time. Each iteration: read the LSB of the input with n & 1, shift the result left by one (making room), OR the bit in, then unsigned-right-shift the input to consume it. After exactly 32 iterations, the result holds the complete reversal.

RECIPE Build the reversed integer bit by bit

  • 0 · Initialize. result = 0. We will accumulate the reversed bits here.
  • 1 · Loop 32 times (one for each bit position in a 32-bit integer).
  • 2 · Extract LSB. bit = n & 1. This isolates the rightmost bit — the one that should move to the other end.
  • 3 · Shift result left, insert bit. result = (result << 1) | bit. The left-shift makes room for the new bit; the OR places it at the newly opened position.
  • 4 · Consume input bit. n >>>= 1. Unsigned right-shift discards the processed LSB without sign-extending.
  • 5 · Return. result >>> 0 to coerce back to an unsigned 32-bit value (JavaScript shifts can produce signed results).
Classic confusion → JavaScript's << and >> operators treat their operands as signed 32-bit integers. Always use >>> (unsigned right-shift) when working with unsigned bit patterns, and apply >>> 0 on the final result to convert to unsigned.

COST Complexity & alternatives

String conversion
O(1)*
Convert to binary string, reverse, parse — works but hides bit ops.
Bit-manipulation loop
O(1)
32 fixed iterations, no allocations, pure arithmetic.

Both are O(1) since the bit width is fixed at 32. The bit-manipulation version is the expected answer in interviews and avoids string allocation entirely.

Pattern transfer → the divide-and-conquer mask trick reverses 32 bits in just 5 steps by swapping even/odd bits, then pairs, then nibbles, then bytes, then half-words — useful as a follow-up discussion. The same mask technique powers Number of 1 Bits (Hamming weight in O(log n) steps) and efficient gray-code conversions.

RUN IT Reverse the 32-bit representation one bit at a time

step 0 / 33
STARTInput: 43261596 (decimal) = 00000010100101000001111010011100 (32-bit binary). We will read each bit LSB-first and shift it into the result from the left, 32 times.
input:03103002902802702612502412302202112001911801701601501401311211111019081706051413120100
result:03103002902802702602502402302202102001901801701601501401301201101009080706050403020100
State
—
i
—
bit
00000010100101000001111010011100
input (rem)
00000000000000000000000000000000
result (bin)
0
result (dec)
bit being read (LSB)bit just placed into resultfinal result
slowfast

TYPESCRIPT The solution, annotated

reverseBits.ts
function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    const bit = n & 1;       // extract the LSB
    result = (result << 1) | bit;  // shift result left, insert bit
    n >>>= 1;                // unsigned right-shift the input
  }
  return result >>> 0;       // coerce to unsigned 32-bit
}

Reading it block by block

Line 2 — result accumulator. We build the reversed integer here. Starts at 0. Each iteration appends one bit on the right (via result << 1 | bit), which corresponds to prepending on the left of the final reversed view.
Line 3 — fixed 32-iteration loop. We always process exactly 32 bits regardless of the input value — even leading zeros in the original are trailing zeros in the reversal and must be accounted for.
Line 4 — extract LSB. n & 1 masks everything but the lowest bit. Result is 0 or 1. This is the bit that will migrate to the mirror position in the output.
Line 5 — shift and insert. result << 1 makes room on the right; | bitfills that position with the extracted LSB. Over 32 iterations this streams all bits from the input's LSB into the result's MSB-first order.
Line 6 — consume the input bit. n >>>= 1 is the unsigned right-shift: it shifts zero into the sign bit rather than replicating it. Always prefer >>> over >> for unsigned bit patterns in JavaScript.
Line 8 — coerce to unsigned. Applying >>> 0 to the result normalizes it to a 32-bit unsigned integer. JavaScript bitwise ops return signed values; without this step a high bit set would produce a negative decimal result.
Follow-up: divide-and-conquer mask trick. Instead of a loop, swap bits in parallel using XOR masks: n = ((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1) swaps adjacent bits; a similar pair of masks with shift 2 swaps pairs; shift 4 swaps nibbles; shift 8 swaps bytes; shift 16 swaps halfwords. Five operations total — elegant and worth knowing for advanced follow-up discussions.
Complexity → O(1) time — exactly 32 iterations regardless of input; O(1) space — only two integer variables.

INTERVIEWFollow-ups they'll ask

  • "What if called many times?" Cache reversed bytes in a 256-entry lookup table; split the 32-bit input into four bytes, reverse each, reassemble in swapped order — one cache lookup per byte.
  • "Divide-and-conquer approach?" Five XOR-mask steps swap bits pairwise at increasing granularity (bit pairs → nibbles → bytes → halfwords) without any loop.
  • "Why >>> instead of >>?" JavaScript's >> sign-extends; for unsigned 32-bit work, >>> fills with zeros and keeps the semantics correct.
  • "What's the output for n=1?" 00000000 00000000 00000000 00000001 reversed is 10000000 00000000 00000000 00000000 = 2147483648 — a good mental check.
  • "Can you do it in fewer than 32 operations?"The divide-and-conquer mask trick takes exactly 5 merge operations (O(log 32)) — yes, and it's elegant enough to write on a whiteboard.

MNEMONIC The one-liner

"Peel LSB, shift result left, insert, repeat 32 times — then >>> 0 to unsigned."

TRIGGERS When you see ___ → reach for ___

"reverse bits of a 32-bit integer"32-iter loop: peel LSB, shift left into result
bit mirror / bit reflection(result << 1) | (n & 1), n >>>= 1
unsigned integer needed in JS/TSalways use >>> 0 or >>>= 1
"reverse bits many times / cache"byte-lookup table: 256 entries, split 32-bit into 4 bytes

SKELETON The reusable shape

skeleton.ts
function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    const bit = n & 1;
    result = (result << 1) | bit;
    n >>>= 1;
  }
  return result >>> 0;
}

FLASHCARDS Tap to flip

How do you extract the LSB of an integer?
n & 1 — AND with 1 isolates the lowest bit.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 7
QUESTION 01
What does n & 1 compute?
QUESTION 02
Why does the loop iterate exactly 32 times?
QUESTION 03
What is result = (result << 1) | bit doing?
QUESTION 04
What is the output for input n = 43261596?
QUESTION 05
Why apply >>> 0 to the final result?
QUESTION 06
Time and space complexity of the 32-iteration loop solution?
QUESTION 07
In the divide-and-conquer mask trick, how many XOR-mask operations are needed to reverse 32 bits?