#73 · Bit Manipulation

Reverse Bits

Reverse the bits of a 32-bit unsigned integer: the lowest bit becomes the highest, and so on.

EasyLeetCode

Bit being examined
Counted / set / result
Related bit
Cleared / carried

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

A 32-bit word as a row of bits

Reversing mirrors the row: bit i moves to position 31 − i. You can move bits one at a time (shifting between two registers), place each bit by index, or rearrange whole blocks of bits with masks.

Memory layout

Two 32-bit registers or one, depending on the method.

Operation	Cost
bit-by-bit methods	O(32)
block-swap method	O(log 32) = 5 steps

Masks and shifts

A mask such as 0x00ff00ff selects alternate groups of bits; shifting by the group size moves them into their neighbour's place. Combining two such moves swaps neighbouring groups.

Memory layout

Constants in the instruction stream.

Operation	Cost
swap neighbouring groups	O(1)

Why it fits

A reversal is a fixed permutation of bit positions, so it can be expressed with shifts, masks and ORs only.
The reversal of a word is the reversal of its two halves, swapped. Applying that idea recursively gives the five-step block swap.
In languages with signed integers the result must be interpreted as unsigned at the end, since the top bit is the sign bit.

Why alternatives degrade

Arithmetic (division and modulo by 2):: It works for non-negative numbers but is a slow way to say shift and mask, and breaks with the sign bit.
A lookup table for all 32-bit values:: Four billion entries. A table for bytes (256 entries) combined with byte reordering is practical, but the mask method needs no memory.
Swapping bit i with bit 31 − i in a loop:: It works (16 swaps) but each swap needs conditional logic, which is more code than the block swap.

Four approaches, from naive to production

1 · beginner

Reverse the binary string

time O(32)space O(32) for the strings

Write n as a 32-character binary string, reverse the text, and parse it back as a number.

uint32_t reverseBits(uint32_t n) {
    string bits = bitset<32>(n).to_string();
    string reversed(bits.rbegin(), bits.rend());
    return (uint32_t)stoull(reversed, nullptr, 2);
}

public int reverseBits(int n) {
    String bits = String.format("%32s", Integer.toBinaryString(n)).replace(' ', '0');
    String reversed = new StringBuilder(bits).reverse().toString();
    return (int) Long.parseLong(reversed, 2);
}

def reverse_bits(n):
    bits = format(n, '032b')
    reversed_bits = bits[::-1]
    return int(reversed_bits, 2)

function reverseBits(n: number): number {
  const bits = n.toString(2).padStart(32, '0');
  const reversed = bits.split('').reverse().join('');
  return parseInt(reversed, 2);
}

Flaws & bottlenecks

Builds two strings and a parse: much slower than direct bit operations.
The padding to 32 digits is essential and easy to forget (leading zeros would be lost).
Hides the bit-level thinking the problem is about.

Interviewer cross-questions

Why pad to 32 characters?

Say: toString(2) drops leading zeros. A number with leading zeros must keep them so that, when reversed, they become trailing zeros of the result.

Is the result correct for numbers with the top bit set?

Say: In JavaScript parseInt returns a positive number up to 2³² − 1, which is the unsigned interpretation required here.

How do you avoid strings?

Say: Move the bits with shifts and ORs between two registers.

2 · intermediate

Pop a bit from n, push it onto result

time O(32)space O(1)

Repeat 32 times: shift result left by one, OR in the lowest bit of n, and shift n right by one. The first bit popped ends up as the highest bit of result.

uint32_t reverseBits(uint32_t n) {
    uint32_t result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>= 1;
    }
    return result;
}

public int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>>= 1;
    }
    return result;
}

def reverse_bits(n):
    result = 0
    for i in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

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

Flaws & bottlenecks

Always 32 iterations, even if n is small.
A signed result must be converted to unsigned at the end (>>> 0 in JavaScript).
The loop count must be exactly 32, not "until n is zero", or leading zeros would be lost.

Interviewer cross-questions

Why 32 iterations and not "while n is non-zero"?

Say: Leading zeros of n must become trailing zeros of the result. Stopping when n reaches 0 would leave the result unshifted by the number of leading zeros.

Why is >>> needed on n?

Say: An arithmetic shift would copy the sign bit into the top, so for a number with the top bit set n would never become 0 and the shifted-in bits would be ones.

How would you reverse the bits of a function called many times?

Say: Precompute a 256-entry table of reversed bytes and combine four lookups: O(4) per call.

3 · advanced

Place each set bit at its mirror position

time O(32)space O(1)

For every position i, if bit i of n is 1 set bit 31 − i of the result with result |= 1 << (31 − i).

uint32_t reverseBits(uint32_t n) {
    uint32_t result = 0;
    for (int i = 0; i < 32; i++) {
        if ((n >> i) & 1) result |= 1u << (31 - i);
    }
    return result;
}

public int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        if (((n >>> i) & 1) != 0) result |= 1 << (31 - i);
    }
    return result;
}

def reverse_bits(n):
    result = 0
    for i in range(32):
        if (n >> i) & 1: result |= 1 << (31 - i)
    return result

function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    if ((n >>> i) & 1) result |= 1 << (31 - i);
  }
  return result >>> 0;
}

Flaws & bottlenecks

Still 32 iterations with a branch each.
The shift 1 << 31 produces a negative number in signed arithmetic; the final conversion is required.
More explicit than the shift version, but not shorter.

Interviewer cross-questions

Which is clearer, this or pop-and-push?

Say: This one states the idea directly (bit i goes to 31 − i). The pop-and-push version needs no index arithmetic and no branch.

What does 1 << (31 − i) do?

Say: It builds a mask with only bit 31 − i set, so OR-ing it into result turns exactly that bit on.

How could you skip the zero bits?

Say: Iterate only over the set bits of n (clear the lowest set bit each time with n & (n − 1)) and mirror each one by its index.

4 · expert

Swap halves, quarters, … (five masked swaps)

time O(log 32) = 5 stepsspace O(1)

Swap the 16-bit halves, then within each half swap the bytes, then nibbles, then 2-bit pairs, then single bits, using a mask for each level. Five steps reverse all 32 bits without a loop.

uint32_t reverseBits(uint32_t n) {
    n = (n >> 16) | (n << 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;
}

public int reverseBits(int n) {
    n = (n >>> 16) | (n << 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;
}

def reverse_bits(n):
    n = ((n >> 16) | (n << 16)) & 0xFFFFFFFF
    n = (((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)) & 0xFFFFFFFF
    n = (((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)) & 0xFFFFFFFF
    n = (((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2)) & 0xFFFFFFFF
    n = (((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1)) & 0xFFFFFFFF
    return n

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

Flaws & bottlenecks

The constants are easy to mistype and are hard to verify by eye.
Written for exactly 32 bits; other widths need other masks and step counts.
In modern CPUs there is a single instruction for it (for example ARM RBIT); the intrinsic is clearer where available.

Interviewer cross-questions

Why does swapping blocks reverse the whole word?

Say: Reversing a word means reversing each half and exchanging them. Swapping blocks at every scale does the same recursively: after the final level every bit has moved to its mirror position.

Why a mask at each step?

Say: The mask picks the left blocks of a pair of neighbouring blocks (to shift right) and the right blocks (to shift left). OR-ing the two shifted results exchanges them.

What is the cost compared with the loop?

Say: Five rounds of a few operations each versus 32 iterations of a few operations: roughly six times fewer instructions, and no branches.

Synchronized code walkthrough

Showing: Reverse the binary string — shares the player above; click any step to jump.

uint32_t reverseBits(uint32_t n) {
    string bits = bitset<32>(n).to_string();
    string reversed(bits.rbegin(), bits.rend());
    return (uint32_t)stoull(reversed, nullptr, 2);
}

public int reverseBits(int n) {
    String bits = String.format("%32s", Integer.toBinaryString(n)).replace(' ', '0');
    String reversed = new StringBuilder(bits).reverse().toString();
    return (int) Long.parseLong(reversed, 2);
}

def reverse_bits(n):
    bits = format(n, '032b')
    reversed_bits = bits[::-1]
    return int(reversed_bits, 2)

function reverseBits(n: number): number {
  const bits = n.toString(2).padStart(32, '0');
  const reversed = bits.split('').reverse().join('');
  return parseInt(reversed, 2);
}

uint32_t reverseBits(uint32_t n) {
    uint32_t result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>= 1;
    }
    return result;
}

public int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>>= 1;
    }
    return result;
}

def reverse_bits(n):
    result = 0
    for i in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

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

uint32_t reverseBits(uint32_t n) {
    uint32_t result = 0;
    for (int i = 0; i < 32; i++) {
        if ((n >> i) & 1) result |= 1u << (31 - i);
    }
    return result;
}

public int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        if (((n >>> i) & 1) != 0) result |= 1 << (31 - i);
    }
    return result;
}

def reverse_bits(n):
    result = 0
    for i in range(32):
        if (n >> i) & 1: result |= 1 << (31 - i)
    return result

function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    if ((n >>> i) & 1) result |= 1 << (31 - i);
  }
  return result >>> 0;
}

uint32_t reverseBits(uint32_t n) {
    n = (n >> 16) | (n << 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;
}

public int reverseBits(int n) {
    n = (n >>> 16) | (n << 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;
}

def reverse_bits(n):
    n = ((n >> 16) | (n << 16)) & 0xFFFFFFFF
    n = (((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)) & 0xFFFFFFFF
    n = (((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)) & 0xFFFFFFFF
    n = (((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2)) & 0xFFFFFFFF
    n = (((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1)) & 0xFFFFFFFF
    return n

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