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.
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
Code
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
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 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.