Reverse bits

190.Reverse Bits

Bit Manipulation

Math

Problem Statement:

Reverse bits of a given 32 bits unsigned integer. Return the integer corresponding to the reversed binary representation.

Example:

Input:

n = 43261596 (00000010100101000001111010011100)

→

Output:

964176192 (00111001011110000010100101000000)

Algorithm:

1. Iterate through all 32 bits
2. Extract each bit from right
3. Place bit in reverse position
4. Build result using OR operations

Complexity:

Time: O(1) - fixed 32 iterations | Space: O(1)

Java Solution:

public int reverseBits(int n) {
    int res = 0;
    
    // Process each bit (32-bit integer)
    for (int i = 0; i < 32; i++) {
        // Extract bit at position i
        int bit = (n >> i) & 1;
        
        // Place bit in reverse position
        res |= bit << (31 - i);
    }
    
    return res;
}

// Alternative approach using left shift for checking bits
public int reverseBitsAlt(int n) {
    int res = 0;
    
    for (int i = 0; i < 32; i++) {
        // Check if bit is set using left shift
        boolean isSet = (n & (1 << i)) != 0;
        
        if (isSet) {
            res |= 1 << (31 - i);
        }
    }
    
    return res;
}

Python Solution:

def reverseBits(self, n: int) -> int:
    res = 0
    
    # Process each bit (32-bit integer)
    for i in range(32):
        # Extract bit at position i
        bit = (n >> i) & 1
        
        # Place bit in reverse position
        res |= bit << (31 - i)
    
    return res

C++ Solution:

uint32_t reverseBits(uint32_t n) {
    uint32_t res = 0;
    
    // Process each bit (32-bit integer)
    for (int i = 0; i < 32; i++) {
        // Extract bit at position i
        uint32_t bit = (n >> i) & 1;
        
        // Place bit in reverse position
        res |= bit << (31 - i);
    }
    
    return res;
}