AlgoMaster Logo

Reverse Bits

Last Updated: March 20, 2026

easy
4 min read

Understanding the Problem

We are given a 32-bit unsigned integer and need to reverse all its bits. This means the least significant bit (position 0) becomes the most significant bit (position 31), position 1 becomes position 30, and so on. It is the same idea as reversing a string, but instead of characters, we are swapping bit positions.

The key thing to understand is that we are always working with exactly 32 bits, even if the number is small. For example, the number 1 is 00000000000000000000000000000001 in binary. Reversing it gives 10000000000000000000000000000000, which is 2147483648. Leading zeros in the original number become trailing zeros in the result, and vice versa.

Key Constraints:

  • 0 <= n <= 2^31 - 2 → The input fits in a 32-bit integer. We are working with a fixed-size input, not a variable-length one.
  • n is even → The least significant bit is always 0, so the most significant bit of the result will always be 0. This is a minor observation but confirms the result always fits in a signed 32-bit integer.

Approach 1: Bit-by-Bit Reversal

Intuition

The most natural approach mirrors how you would reverse a string: read characters from one end and write them to the other. Here, we extract bits from the right side of the input (least significant) and place them into the result from the left side (most significant).

For each of the 32 bit positions, we grab the last bit of n, shift our result left by one to make room, and add that bit to the result. Then we shift n right by one to expose the next bit.

Algorithm

  1. Initialize result to 0
  2. Loop 32 times (once per bit position)
  3. Shift result left by 1 to make room for the next bit
  4. Extract the last bit of n using n & 1 and OR it into result
  5. Shift n right by 1 to move to the next bit
  6. Return result

Example Walkthrough

1n = 00001101 (13), result = 00000000. Extract bits right-to-left.
0
0
1
0
2
0
3
0
4
1
5
1
6
0
7
1
extract
1/7

Code

The bit-by-bit approach already runs in O(1) time, so for a single call it is perfectly fine. But if this function is called billions of times, each call performs 32 iterations with a branch and two shifts. Can we precompute byte-level reversals to reduce the per-call work?

Approach 2: Byte-Level Lookup Table

Intuition

If we are calling reverseBits millions of times, we can precompute the reversal of every possible byte (8-bit value). There are only 256 possible bytes, so the lookup table is tiny. Then to reverse 32 bits, we split the integer into 4 bytes, look up each byte's reversal, and reassemble them in reverse order.

This trades a small amount of memory (256 entries) for a significant speedup: instead of 32 loop iterations, we do 4 lookups and a few shifts.

Algorithm

  1. Build a lookup table of size 256 where table[i] is the bit-reversal of the 8-bit value i
  2. To reverse a 32-bit integer, extract each of the 4 bytes
  3. Look up the reversal of each byte
  4. Place each reversed byte in the opposite position (byte 0 goes to position 3, byte 1 to position 2, etc.)
  5. Combine the 4 reversed bytes with OR

Code

The lookup table approach is great for repeated calls, but it requires 256 entries of precomputed data. The 4 lookups also involve memory access, which can be slow on cache misses. Is there a way to reverse all 32 bits using only arithmetic and bitwise operations, with no memory lookups at all?

Approach 3: Divide and Conquer (Bitmask Swapping)

Intuition

This is the most elegant approach and directly answers the follow-up question. The idea comes from divide and conquer: to reverse 32 bits, first swap the left 16 bits with the right 16 bits. Then within each 16-bit half, swap the left 8 bits with the right 8 bits. Continue halving: swap 4-bit nibbles, then 2-bit pairs, then individual adjacent bits.

Think of it like reversing a deck of cards. You could move cards one by one, or you could cut the deck in half and swap the halves, then recursively do the same within each half. After log2(32) = 5 swaps, every bit has moved to its reversed position.

Each step uses a bitmask to isolate the bits that need to move and shifts to move them to their new positions.

How the masks work:

Let’s imagine the 32-bit number as:

Algorithm

  1. Swap the left 16 bits and right 16 bits (shift by 16)
  2. Swap adjacent 8-bit groups within each 16-bit half (mask 0x00FF00FF, shift by 8)
  3. Swap adjacent 4-bit nibbles within each 8-bit group (mask 0x0F0F0F0F, shift by 4)
  4. Swap adjacent 2-bit pairs within each nibble (mask 0x33333333, shift by 2)
  5. Swap adjacent bits within each pair (mask 0x55555555, shift by 1)

Code