Reverse Bits

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

Language Selection

Choose your preferred programming language

Showing: Python

Reverse Bits

Problem Statement

Reverse bits of a given 32-bit unsigned integer.

Note:

Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be signed integer types and should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 below, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Examples

Example 1:

Input: n = 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: n = 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Constraints

The input must be a binary string of length 32

Approach 1: Bit Manipulation (Optimal)

Algorithm

Extract bits one by one from the right and build the result from the left.

Steps:

Initialize result to 0
For each of the 32 bits:
- Extract the rightmost bit from n
- Add it to the result
- Shift result left and n right
Return the result

Implementation

Python:

def reverseBits(n):
    """
    Reverse bits of a 32-bit unsigned integer
    Time: O(1)
    Space: O(1)
    """
    result = 0
    
    for i in range(32):
        # Extract the rightmost bit
        bit = n & 1
        
        # Add it to the result
        result = (result << 1) | bit
        
        # Shift n right
        n >>= 1
    
    return result

Java:

public class Solution {
    /**
     * Reverse bits of a 32-bit unsigned integer
     * Time: O(1)
     * Space: O(1)
     */
    public int reverseBits(int n) {
        int result = 0;
        
        for (int i = 0; i < 32; i++) {
            // Extract the rightmost bit
            int bit = n & 1;
            
            // Add it to the result
            result = (result << 1) | bit;
            
            // Shift n right
            n >>= 1;
        }
        
        return result;
    }
}

Go:

func reverseBits(n uint32) uint32 {
    /**
     * Reverse bits of a 32-bit unsigned integer
     * Time: O(1)
     * Space: O(1)
     */
    var result uint32
    
    for i := 0; i < 32; i++ {
        // Extract the rightmost bit
        bit := n & 1
        
        // Add it to the result
        result = (result << 1) | bit
        
        // Shift n right
        n >>= 1
    }
    
    return result
}

JavaScript:

/**
 * Reverse bits of a 32-bit unsigned integer
 * Time: O(1)
 * Space: O(1)
 */
function reverseBits(n) {
    let result = 0;
    
    for (let i = 0; i < 32; i++) {
        // Extract the rightmost bit
        const bit = n & 1;
        
        // Add it to the result
        result = (result << 1) | bit;
        
        // Shift n right
        n >>>= 1; // Use unsigned right shift
    }
    
    return result;
}

C#:

public class Solution {
    /// <summary>
    /// Reverse bits of a 32-bit unsigned integer
    /// Time: O(1)
    /// Space: O(1)
    /// </summary>
    public uint reverseBits(uint n) {
        uint result = 0;
        
        for (int i = 0; i < 32; i++) {
            // Extract the rightmost bit
            uint bit = n & 1;
            
            // Add it to the result
            result = (result << 1) | bit;
            
            // Shift n right
            n >>= 1;
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(1) - Exactly 32 iterations
Space Complexity: O(1) - Only using constant extra space

Approach 2: Lookup Table (Optimized)

Algorithm

Use a lookup table to reverse bytes, then reverse the order of bytes.

Steps:

Create a lookup table for reversing 8-bit values
Reverse each byte using the lookup table
Reverse the order of the 4 bytes

Implementation

Python:

def reverseBits_lookup(n):
    """
    Reverse bits using lookup table
    Time: O(1)
    Space: O(1)
    """
    # Lookup table for reversing 8-bit values
    lookup = [0] * 256
    for i in range(256):
        lookup[i] = reverse8Bits(i)
    
    # Reverse each byte and reorder
    result = 0
    for i in range(4):
        byte = (n >> (i * 8)) & 0xFF
        result |= lookup[byte] << ((3 - i) * 8)
    
    return result

def reverse8Bits(n):
    """Reverse 8 bits"""
    result = 0
    for i in range(8):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

Java:

public class Solution {
    private static final int[] LOOKUP = new int[256];
    
    static {
        // Initialize lookup table
        for (int i = 0; i < 256; i++) {
            LOOKUP[i] = reverse8Bits(i);
        }
    }
    
    /**
     * Reverse bits using lookup table
     * Time: O(1)
     * Space: O(1)
     */
    public int reverseBitsLookup(int n) {
        int result = 0;
        
        // Reverse each byte and reorder
        for (int i = 0; i < 4; i++) {
            int byte = (n >> (i * 8)) & 0xFF;
            result |= LOOKUP[byte] << ((3 - i) * 8);
        }
        
        return result;
    }
    
    private static int reverse8Bits(int n) {
        int result = 0;
        for (int i = 0; i < 8; i++) {
            result = (result << 1) | (n & 1);
            n >>= 1;
        }
        return result;
    }
}

Go:

var lookup [256]uint32

func init() {
    // Initialize lookup table
    for i := 0; i < 256; i++ {
        lookup[i] = reverse8Bits(uint32(i))
    }
}

func reverseBitsLookup(n uint32) uint32 {
    /**
     * Reverse bits using lookup table
     * Time: O(1)
     * Space: O(1)
     */
    var result uint32
    
    // Reverse each byte and reorder
    for i := 0; i < 4; i++ {
        byte := (n >> (i * 8)) & 0xFF
        result |= lookup[byte] << ((3 - i) * 8)
    }
    
    return result
}

func reverse8Bits(n uint32) uint32 {
    var result uint32
    for i := 0; i < 8; i++ {
        result = (result << 1) | (n & 1)
        n >>= 1
    }
    return result
}

JavaScript:

// Lookup table for reversing 8-bit values
const lookup = new Array(256);
for (let i = 0; i < 256; i++) {
    lookup[i] = reverse8Bits(i);
}

/**
 * Reverse bits using lookup table
 * Time: O(1)
 * Space: O(1)
 */
function reverseBitsLookup(n) {
    let result = 0;
    
    // Reverse each byte and reorder
    for (let i = 0; i < 4; i++) {
        const byte = (n >> (i * 8)) & 0xFF;
        result |= lookup[byte] << ((3 - i) * 8);
    }
    
    return result;
}

function reverse8Bits(n) {
    let result = 0;
    for (let i = 0; i < 8; i++) {
        result = (result << 1) | (n & 1);
        n >>>= 1;
    }
    return result;
}

C#:

public class Solution {
    private static readonly uint[] Lookup = new uint[256];
    
    static Solution() {
        // Initialize lookup table
        for (int i = 0; i < 256; i++) {
            Lookup[i] = Reverse8Bits((uint)i);
        }
    }
    
    /// <summary>
    /// Reverse bits using lookup table
    /// Time: O(1)
    /// Space: O(1)
    /// </summary>
    public uint reverseBitsLookup(uint n) {
        uint result = 0;
        
        // Reverse each byte and reorder
        for (int i = 0; i < 4; i++) {
            uint byte = (n >> (i * 8)) & 0xFF;
            result |= Lookup[byte] << ((3 - i) * 8);
        }
        
        return result;
    }
    
    private static uint Reverse8Bits(uint n) {
        uint result = 0;
        for (int i = 0; i < 8; i++) {
            result = (result << 1) | (n & 1);
            n >>= 1;
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(1) - Constant time with lookup table
Space Complexity: O(1) - Lookup table is constant size

Approach 3: Divide and Conquer (Alternative)

Algorithm

Use divide and conquer to reverse bits by swapping halves recursively.

Steps:

Swap left and right 16-bit halves
Swap left and right 8-bit halves within each 16-bit half
Swap left and right 4-bit halves within each 8-bit half
Swap left and right 2-bit halves within each 4-bit half
Swap left and right 1-bit halves within each 2-bit half

Implementation

Python:

def reverseBits_divideConquer(n):
    """
    Reverse bits using divide and conquer
    Time: O(1)
    Space: O(1)
    """
    # Swap 16-bit halves
    n = ((n & 0xFFFF0000) >> 16) | ((n & 0x0000FFFF) << 16)
    
    # Swap 8-bit halves
    n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8)
    
    # Swap 4-bit halves
    n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4)
    
    # Swap 2-bit halves
    n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2)
    
    # Swap 1-bit halves
    n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1)
    
    return n

Java:

public class Solution {
    /**
     * Reverse bits using divide and conquer
     * Time: O(1)
     * Space: O(1)
     */
    public int reverseBitsDivideConquer(int n) {
        // Swap 16-bit halves
        n = ((n & 0xFFFF0000) >>> 16) | ((n & 0x0000FFFF) << 16);
        
        // Swap 8-bit halves
        n = ((n & 0xFF00FF00) >>> 8) | ((n & 0x00FF00FF) << 8);
        
        // Swap 4-bit halves
        n = ((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4);
        
        // Swap 2-bit halves
        n = ((n & 0xCCCCCCCC) >>> 2) | ((n & 0x33333333) << 2);
        
        // Swap 1-bit halves
        n = ((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1);
        
        return n;
    }
}

Go:

func reverseBitsDivideConquer(n uint32) uint32 {
    /**
     * Reverse bits using divide and conquer
     * Time: O(1)
     * Space: O(1)
     */
    // Swap 16-bit halves
    n = ((n & 0xFFFF0000) >> 16) | ((n & 0x0000FFFF) << 16)
    
    // Swap 8-bit halves
    n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8)
    
    // Swap 4-bit halves
    n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4)
    
    // Swap 2-bit halves
    n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2)
    
    // Swap 1-bit halves
    n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1)
    
    return n
}

JavaScript:

/**
 * Reverse bits using divide and conquer
 * Time: O(1)
 * Space: O(1)
 */
function reverseBitsDivideConquer(n) {
    // Swap 16-bit halves
    n = ((n & 0xFFFF0000) >>> 16) | ((n & 0x0000FFFF) << 16);
    
    // Swap 8-bit halves
    n = ((n & 0xFF00FF00) >>> 8) | ((n & 0x00FF00FF) << 8);
    
    // Swap 4-bit halves
    n = ((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4);
    
    // Swap 2-bit halves
    n = ((n & 0xCCCCCCCC) >>> 2) | ((n & 0x33333333) << 2);
    
    // Swap 1-bit halves
    n = ((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1);
    
    return n;
}

C#:

public class Solution {
    /// <summary>
    /// Reverse bits using divide and conquer
    /// Time: O(1)
    /// Space: O(1)
    /// </summary>
    public uint reverseBitsDivideConquer(uint n) {
        // Swap 16-bit halves
        n = ((n & 0xFFFF0000) >> 16) | ((n & 0x0000FFFF) << 16);
        
        // Swap 8-bit halves
        n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8);
        
        // Swap 4-bit halves
        n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4);
        
        // Swap 2-bit halves
        n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2);
        
        // Swap 1-bit halves
        n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1);
        
        return n;
    }
}

Complexity Analysis

Time Complexity: O(1) - Constant time bit operations
Space Complexity: O(1) - No extra space used

Key Insights

Bit Extraction: Extract bits from right and build result from left
Lookup Table: Pre-compute reversals for faster execution
Divide and Conquer: Swap halves recursively
Bit Masks: Use hexadecimal masks for efficient bit manipulation
Unsigned Right Shift: Use >>> in JavaScript for unsigned shift

Edge Cases

Zero: All zeros should reverse to all zeros
All Ones: All ones should reverse to all ones
Single Bit: Single set bit should reverse to single bit
Alternating Pattern: 1010… should reverse to 0101…
Large Numbers: Handle 32-bit integers correctly

Test Cases

def test_reverseBits():
    # Basic cases
    assert reverseBits(0b00000010100101000001111010011100) == 0b00111001011110000010100101000000
    assert reverseBits(0b11111111111111111111111111111101) == 0b10111111111111111111111111111111
    
    # Edge cases
    assert reverseBits(0) == 0
    assert reverseBits(0xFFFFFFFF) == 0xFFFFFFFF
    assert reverseBits(1) == 0x80000000
    assert reverseBits(0x80000000) == 1
    
    # Test all approaches
    n = 0b00000010100101000001111010011100
    assert reverseBits(n) == reverseBits_lookup(n)
    assert reverseBits(n) == reverseBits_divideConquer(n)
    
    print("All tests passed!")

test_reverseBits()

Follow-up Questions

Reverse Bits in Range: Reverse only a specific range of bits?
Reverse Bytes: Reverse the order of bytes in a 32-bit integer?
Reverse Nibbles: Reverse the order of nibbles (4-bit groups)?
Reverse Bits in String: Reverse bits in a binary string representation?
Reverse Bits in Array: Reverse bits in an array of integers?

Common Mistakes

Signed vs Unsigned: Not handling signed integers correctly
Bit Shift Direction: Confusing left and right shifts
Bit Mask Values: Incorrect hexadecimal mask values
Loop Bounds: Not iterating exactly 32 times
Result Initialization: Not initializing result to 0

Interview Tips

Start Simple: Begin with the basic bit manipulation approach
Explain Bit Operations: Show understanding of bit shifts and masks
Discuss Optimization: Mention lookup table and divide-conquer approaches
Handle Edge Cases: Mention zero, all ones, and single bit cases
Follow-up Ready: Be prepared for variations and optimizations

Concept Explanations

Bit Manipulation Approach: The most straightforward approach extracts bits one by one from the rightmost position of the input and builds the result by shifting left and adding the extracted bit. This effectively reverses the bit order.

Lookup Table Optimization: Instead of reversing bits one by one, we can pre-compute the reversal of all possible 8-bit values and use these to reverse the 4 bytes of a 32-bit integer. This reduces the number of operations from 32 to 4.

Divide and Conquer: This approach uses the principle of divide and conquer by swapping halves of the bit string at different levels. We start by swapping 16-bit halves, then 8-bit halves, then 4-bit halves, and so on, until we’ve reversed all individual bits.

Bit Masks: Hexadecimal masks like 0xFFFF0000, 0xFF00FF00, etc., are used to select specific bit ranges for swapping. These masks are carefully chosen to isolate the bits we want to swap.

Why These Work: All approaches achieve the same result but with different trade-offs. The basic approach is simple and easy to understand, the lookup table is faster for repeated operations, and the divide-conquer approach is elegant and efficient.