Core Bit Tricks

Reverse Bits

Build the result bit by bit: take the lowest bit of n (n & 1), put it at the highest remaining position in the result (left shift result, OR with the bit), then right shift n. Repeat 32 times.

O(1)

say this out loud

I pull bits off one end and push them onto the other. For repeated calls I would cache byte-sized chunks in a lookup table.

How It Works

Reversing the bits of a 32-bit word builds the answer incrementally: on each of 32 iterations, shift the result left by one, OR in the lowest bit of the input (n & 1), and shift the input right by one. The first input bit consumed becomes the highest output bit, so after 32 rounds the order is fully mirrored. Time is O(32) (constant) with O(1) space.

A divide-and-conquer variant swaps progressively smaller blocks with masks: exchange the two 16-bit halves, then adjacent bytes, nibbles, pairs, and single bits, using constants like 0x55555555 and 0xAAAAAAAA. That takes five mask-and-shift steps instead of thirty-two loop iterations and is branch-free. When the function is called many times, caching reversed bytes in a 256-entry lookup table amortizes the work to four table reads per word.

Step-by-Step Visualization

Reverse the bits of 1011, which should give 1101

resultempty

1/8

Code

Java

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

Tips & Gotchas

1Extract lowest bit with n & 1, place at high position

2Shift n right and result left each iteration

3Process all 32 bits for standard integers

Practice Problems

1Reverse Bits
2Reverse Integer
3Add Binary

About the Core Bit Tricks Pattern

Fundamental bit operations that appear in many problems. These are building blocks. Memorize them.

Key insight

Key tricks: n & (n-1) clears lowest set bit (power-of-2 check). XOR of all elements cancels pairs. Bit masks can represent subsets for DP. These are often O(1) space solutions.

Common Bit Manipulation Interview Problems

Single Number
Number of 1 Bits
Counting Bits
Missing Number
Reverse Bits
Power of Two

Frequently Asked Questions

How does the mask-based swap approach reverse bits in five steps?

It reverses hierarchically: swapping the 16-bit halves, then adjacent bytes within each half, then nibbles, bit-pairs, and finally neighboring bits composes into a full reversal. Each level is one AND-shift-OR expression over the whole word, so the total is five constant-time steps with no loop.

What is the difference between reversing bits and reversing a decimal integer?

Reverse Bits mirrors the fixed 32-bit binary representation, including leading zeros, and cannot overflow. Reverse Integer reorders base-10 digits of a signed value, where leading zeros vanish and the result can exceed the 32-bit range, so it needs an explicit overflow check before each append.