Frontend Beauty
ESC

Type to search the knowledge base.

Reverse Bits

Reverse the 32 bits of an integer — shift-and-accumulate or divide-and-conquer bit swaps.

beginner3 min read
  • dsa
  • bit
  • interview
  • Google
  • Meta

The problem

Reverse bits of a given 32-bit unsigned integer and return the result as an unsigned integer.

Input:  n = 00000010100101000001111010011100
Output: 964176192
// 00111001011110000010100101000000

In TypeScript/JS, force unsigned with >>> 0 when comparing or returning.

Brute force: 32 shift loop

Read bit i from the source, write it to position 31 - i in the result.

function reverseBitsBrute(n: number): number {
  let res = 0;
  for (let i = 0; i < 32; i++) {
    res = (res << 1) | (n & 1);
    n >>>= 1;
  }
  return res >>> 0;
}
Time O(32) = O(1)
Space O(1)

This is the expected optimal for interviews. There is also a parallel bit-swap approach.

Optimal flex: mask and swap

Swap 16-bit halves, then 8-bit, 4-bit, 2-bit, 1-bit groups:

function reverseBits(n: number): number {
  n = n >>> 0;
  n = ((n & 0xffff0000) >>> 16) | ((n & 0x0000ffff) << 16);
  n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
  n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
  n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
  n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
  return n >>> 0;
}

Same O(1). Impressive if you remember masks; the loop is safer under pressure.

Cached reverse for streaming

If reversing many numbers, precompute reverse of every byte (256 entries) and assemble. Mention as system-ish follow-up.

Edge cases

  • n = 0 → 0
  • n = 1 → 1 << 31 = 2147483648 (as uint)
  • All ones
  • JS: result may look negative if printed as signed int; problem wants unsigned meaning — >>> 0

Common bugs

  • Looping fewer than 32 times (leading zeros still matter)
  • Using arithmetic >> and sign-extending
  • Forgetting unsigned return

Interview delivery

  1. Exactly 32 bits including leading zeros.
  2. Loop shift-or is fine.
  3. Optional parallel swaps.
  4. >>> 0 in JS.
  5. Related: reverse bytes for endianness discussions.

Loop invariant

After k iterations, res holds the low k bits of the original n reversed into its low k positions, and n has been shifted right k times. At k=32, done.

Why 32 fixed

Leading zeros in the input still consume positions in the output (they become trailing zeros in the reversed bit pattern). Stopping early when n becomes 0 is wrong for this problem.

Endianness aside

Byte-reverse vs bit-reverse are different. Network code often swaps bytes; this problem reverses all 32 bits. Clarify if a follow-up asks “reverse bytes only.”

Further reading