Skip to main content
CodePeetCodePeet
CodePeet 150

Reverse Bits

EASYProblemSolveExternal Links

Description

Reverse the bits of a given 32-bit unsigned integer.

In other words, the bit at position 0 (the rightmost bit) should move to position 31 (the leftmost bit), the bit at position 1 should move to position 30, and so on. Each bit keeps its value (0 or 1) but changes its position to create a mirror image of the original binary representation.

Examples

Example 1

Input: n = 43261596

Output: 964176192

Explanation:

IntegerBinary Representation
4326159600000010100101000001111010011100
96417619200111001011110000010100101000000

Reading the binary of the input from right to left gives exactly the binary of the output.

Example 2

Input: n = 2147483644

Output: 1073741822

Explanation:

IntegerBinary Representation
214748364401111111111111111111111111111100
107374182200111111111111111111111111111110

The two trailing zeros on the right become two leading zeros on the left, and the overall pattern is mirrored.

Constraints

  • The input is a 32-bit unsigned integer
  • 0 ≤ n ≤ 2^31 - 2
  • n is even

Editorial

Brute Force

Intuition

The most straightforward way to reverse the bits is to convert the number to its binary string representation, reverse that string, and convert back to an integer.

Think of it like reversing a word on paper. If someone writes 'HELLO', you can reverse it by writing each letter from right to left to get 'OLLEH'. We do the same thing with the 32-character binary string: read it backwards and interpret the result as a new number.

The catch is that we must ensure the binary string is exactly 32 characters long, padding with leading zeros if necessary. Without padding, a number like 1 (binary '1') would reverse to '1' instead of the correct 32-bit reversal '10000000000000000000000000000000'.

Step-by-Step Explanation

Let's trace through a small example: n = 13

Binary of 13 = 1101. As a 32-bit string: 00000000000000000000000000001101

Step 1: Convert n = 13 to binary string.

  • Raw binary: "1101"
  • Pad to 32 bits: "00000000000000000000000000001101"

Step 2: Reverse the string.

  • Original: "00000000000000000000000000001101"
  • Reversed: "10110000000000000000000000000000"

Step 3: Convert reversed string back to integer.

  • "10110000000000000000000000000000" in decimal = 2952790016

Result: Return 2952790016.

Notice how the rightmost bits '1101' became the leftmost bits '1011' after reversal — the bit pattern is mirrored across the center of the 32-bit representation.

String Reversal of Binary Representation — Watch how we convert to a binary string, reverse it character by character, and convert back to build the reversed number.

Algorithm

  1. Convert n to its binary string representation
  2. Pad the string with leading zeros to ensure it is exactly 32 characters long
  3. Reverse the string
  4. Convert the reversed string back to an integer
  5. Return the result

Code

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        string binary = "";
        
        // Convert to 32-bit binary string
        for (int i = 31; i >= 0; i--) {
            binary += ((n >> i) & 1) ? '1' : '0';
        }
        
        // Reverse the string
        reverse(binary.begin(), binary.end());
        
        // Convert back to integer
        uint32_t result = 0;
        for (int i = 0; i < 32; i++) {
            if (binary[i] == '1') {
                result |= (1u << (31 - i));
            }
        }
        
        return result;
    }
};
class Solution:
    def reverseBits(self, n: int) -> int:
        # Convert to 32-bit binary string
        binary = format(n, '032b')
        
        # Reverse the string
        reversed_binary = binary[::-1]
        
        # Convert back to integer
        return int(reversed_binary, 2)
public class Solution {
    public int reverseBits(int n) {
        StringBuilder binary = new StringBuilder();
        
        // Convert to 32-bit binary string
        for (int i = 31; i >= 0; i--) {
            binary.append((n >> i) & 1);
        }
        
        // Reverse the string
        String reversed = binary.reverse().toString();
        
        // Convert back to integer
        return (int) Long.parseLong(reversed, 2);
    }
}

Complexity Analysis

Time Complexity: O(1)

Although we iterate through 32 bits twice (once to build the string, once to convert back), 32 is a constant. The number of operations does not grow with the input value. Strictly, this is O(32) which simplifies to O(1).

Space Complexity: O(1)

We store a 32-character string, which is a fixed size regardless of input. This is constant space.

Why This Approach Is Not Efficient

While the brute force technically runs in O(1) time (since 32 is constant), it is unnecessarily wasteful. Converting to a string, reversing, and converting back involves creating intermediate string objects, character-by-character manipulation, and parsing — all of which are much slower than direct bit manipulation.

Bit manipulation operations (AND, OR, shift) are single CPU instructions that execute in nanoseconds. String operations involve memory allocation, character arrays, and parsing overhead. For a problem that is fundamentally about bits, working directly with bits is both more elegant and significantly faster in practice.

The key insight: we can extract each bit from the input and place it directly at its reversed position using shifts and OR — no strings needed.

Optimal Approach - Bit-by-Bit Extraction

Intuition

Instead of converting to a string, we work directly with the bits using bitwise operations. The idea is elegant:

We process the input number one bit at a time, from the least significant bit (rightmost) to the most significant bit (leftmost). For each bit we extract, we place it at the corresponding reversed position in our result.

Here is how it works:

  • We extract the rightmost bit of n using n & 1. This gives us either 0 or 1.
  • If we are processing the i-th bit (starting from i = 0), its reversed position is 31 - i. So we shift the extracted bit left by 31 - i positions.
  • We add this repositioned bit to our result using the OR operation (|=).
  • Finally, we shift n right by 1 (n >>= 1) to bring the next bit into the rightmost position for the next iteration.

After 32 iterations, every bit has been extracted from its original position and placed at its mirror position. The result is the fully reversed number.

Think of it like reading a book backwards and rewriting it. You read the last character, write it as the first character of your new book. Read the second-to-last, write it second. And so on until every character has been repositioned.

Diagram showing bit positions 0-31 mapping to reversed positions 31-0 with arrows
Diagram showing bit positions 0-31 mapping to reversed positions 31-0 with arrows

Step-by-Step Explanation

Let's trace through with n = 11 (binary: 00000000000000000000000000001011):

Step 1: Initialize result = 0. We will process all 32 bits, but only the last 4 bits (1011) are non-zero.

Step 2: Iteration i=0. Extract rightmost bit: n & 1 = 1.

  • Place at position 31 - 0 = 31: result |= (1 << 31)
  • result = 10000000000000000000000000000000 (binary)
  • Shift n right: n becomes ...0000101

Step 3: Iteration i=1. Extract rightmost bit: n & 1 = 1.

  • Place at position 31 - 1 = 30: result |= (1 << 30)
  • result = 11000000000000000000000000000000 (binary)
  • Shift n right: n becomes ...0000010

Step 4: Iteration i=2. Extract rightmost bit: n & 1 = 0.

  • Place at position 31 - 2 = 29: result |= (0 << 29) — no change
  • result = 11000000000000000000000000000000 (binary, unchanged)
  • Shift n right: n becomes ...0000001

Step 5: Iteration i=3. Extract rightmost bit: n & 1 = 1.

  • Place at position 31 - 3 = 28: result |= (1 << 28)
  • result = 11010000000000000000000000000000 (binary)
  • Shift n right: n becomes 0

Step 6: Iterations i=4 through i=31. n is now 0, so n & 1 = 0 for all remaining iterations. No more bits are set. We must NOT break early — we continue all 32 iterations to ensure correctness.

Result: result = 11010000000000000000000000000000 (binary) = 3489660928 (decimal).

The original bits '1011' at positions 0-3 have been placed at positions 31-28 as '1101', perfectly mirroring the pattern.

Bit-by-Bit Extraction and Placement — Watch how each bit is extracted from the right side of the input and placed at the mirror position on the left side of the result, building the reversed number one bit at a time.

Algorithm

  1. Initialize result = 0
  2. For i from 0 to 31:
    a. Extract the rightmost bit of n: bit = n & 1
    b. Place this bit at position (31 - i) in result: result |= (bit << (31 - i))
    c. Shift n right by 1: n >>= 1
  3. Return result

Code

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        
        for (int i = 0; i < 32; i++) {
            // Extract rightmost bit and place at reversed position
            result |= (n & 1) << (31 - i);
            // Move to the next bit
            n >>= 1;
        }
        
        return result;
    }
};
class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        
        for i in range(32):
            # Extract rightmost bit and place at reversed position
            result |= (n & 1) << (31 - i)
            # Move to the next bit
            n >>= 1
        
        return result
public class Solution {
    public int reverseBits(int n) {
        int result = 0;
        
        for (int i = 0; i < 32; i++) {
            // Extract rightmost bit and place at reversed position
            result |= (n & 1) << (31 - i);
            // Move to the next bit
            n >>>= 1; // Use unsigned right shift in Java
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(1)

We always iterate exactly 32 times, regardless of the input value. Each iteration performs a constant number of bitwise operations (AND, shift, OR). Total operations: 32 × 3 = 96, which is a fixed constant.

Space Complexity: O(1)

We use only a single integer variable (result) and a loop counter. No strings, no arrays, no additional data structures. Space usage is constant.

Why This Approach Is Not Efficient

The bit-by-bit approach processes each of the 32 bits individually, requiring exactly 32 iterations. While this is already O(1), we can ask: can we do fewer operations?

The answer is yes. Using a divide-and-conquer strategy with bitmasks, we can reverse all 32 bits in just 5 steps by swapping groups of bits at progressively finer granularity. First swap 16-bit halves, then 8-bit groups within those halves, then 4-bit nibbles, then 2-bit pairs, and finally individual adjacent bits.

This reduces the number of operations from 32 loop iterations to 5 fixed operations — a practical speedup that matters in performance-critical code or when the function is called millions of times (as the follow-up question suggests).

Optimal Approach - Divide and Conquer with Bitmasks

Intuition

This approach reverses bits by swapping progressively smaller groups, similar to how you might reverse a deck of cards:

  1. Split the deck in half and swap the two halves (swap the left 16 bits with the right 16 bits).
  2. Within each half, swap quarters (swap 8-bit groups).
  3. Within each quarter, swap pairs of nibbles (swap 4-bit groups).
  4. Within each nibble, swap pairs of bits (swap 2-bit groups).
  5. Within each pair, swap adjacent bits (swap individual bits).

After 5 rounds of swapping at progressively finer granularity, every bit ends up at its mirrored position.

Each swap step uses a bitmask to isolate the groups. For example, to swap the two 16-bit halves, we shift right by 16 and shift left by 16, then combine. The beauty is that all swaps at the same granularity happen simultaneously using a single bitwise expression — no loops required.

This is the same technique used in hardware circuits to reverse bit order.

Diagram showing 5 levels of bit group swapping: 16-bit halves, 8-bit groups, 4-bit nibbles, 2-bit pairs, and single bits
Diagram showing 5 levels of bit group swapping: 16-bit halves, 8-bit groups, 4-bit nibbles, 2-bit pairs, and single bits

Step-by-Step Explanation

Let's trace through with n = 43261596. Binary: 00000010100101000001111010011100.

Step 1: Swap 16-bit halves.

  • Original: 00000010100101000001111010011100
  • Left 16: 0000001010010100 (shifted right 16)
  • Right 16: 0001111010011100 (shifted left 16)
  • After swap: 00011110100111000000001010010100

Step 2: Swap 8-bit groups within each 16-bit half.

  • Before: 00011110100111000000001010010100
  • Swap adjacent 8-bit blocks:
  • After: 10011100000111100001010000000010 (conceptually incorrect — let's show masking)
  • Actually: each 8-bit block within each 16-bit half gets swapped using mask 0x00FF00FF
  • After: 10011100000111101001010000000010

Step 3: Swap 4-bit nibbles within each 8-bit byte.

  • Mask: 0x0F0F0F0F. Each pair of 4-bit nibbles gets swapped.
  • After: 11000100011100011010000100100000

Step 4: Swap 2-bit pairs within each nibble.

  • Mask: 0x33333333. Each pair of 2-bit groups gets swapped.
  • After: 11000001011100100010010001000000

Step 5: Swap adjacent single bits.

  • Mask: 0x55555555. Each pair of adjacent bits gets swapped.
  • After: 00111001011110000010100101000000

Result: 00111001011110000010100101000000 = 964176192. This matches the expected output.

Divide and Conquer — Swapping at Every Granularity — Watch how the 32-bit number is reversed in 5 stages by swapping progressively smaller groups of bits until every bit reaches its mirror position.

Algorithm

  1. Swap the two 16-bit halves: n = (n >> 16) | (n << 16)
  2. Swap adjacent 8-bit groups: n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8)
  3. Swap adjacent 4-bit nibbles: n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4)
  4. Swap adjacent 2-bit pairs: n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2)
  5. Swap adjacent individual bits: n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1)
  6. Return n

Code

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        // Swap 16-bit halves
        n = (n >> 16) | (n << 16);
        // Swap adjacent 8-bit groups
        n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8);
        // Swap adjacent 4-bit nibbles
        n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4);
        // Swap adjacent 2-bit pairs
        n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2);
        // Swap adjacent individual bits
        n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1);
        return n;
    }
};
class Solution:
    def reverseBits(self, n: int) -> int:
        # Swap 16-bit halves
        n = ((n >> 16) | (n << 16)) & 0xFFFFFFFF
        # Swap adjacent 8-bit groups
        n = (((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8)) & 0xFFFFFFFF
        # Swap adjacent 4-bit nibbles
        n = (((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4)) & 0xFFFFFFFF
        # Swap adjacent 2-bit pairs
        n = (((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2)) & 0xFFFFFFFF
        # Swap adjacent individual bits
        n = (((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1)) & 0xFFFFFFFF
        return n
public class Solution {
    public int reverseBits(int n) {
        // Swap 16-bit halves
        n = (n >>> 16) | (n << 16);
        // Swap adjacent 8-bit groups
        n = ((n & 0xFF00FF00) >>> 8) | ((n & 0x00FF00FF) << 8);
        // Swap adjacent 4-bit nibbles
        n = ((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4);
        // Swap adjacent 2-bit pairs
        n = ((n & 0xCCCCCCCC) >>> 2) | ((n & 0x33333333) << 2);
        // Swap adjacent individual bits
        n = ((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1);
        return n;
    }
}

Complexity Analysis

Time Complexity: O(1)

We perform exactly 5 bitwise operations, regardless of the input. There are no loops and no recursion. Each operation is a constant number of shifts, ANDs, and ORs. This is the theoretical minimum for bit reversal.

Space Complexity: O(1)

We modify the number in-place using only the input variable. No additional memory is allocated.