190. Reverse Bits

Description

Given a 32-bit unsigned integer, reverse its bits and return the result as an unsigned integer.

Intuition

The problem requires reversing the bits of a given 32-bit unsigned integer. By iterating through each bit of the input number, we can construct the reversed bit sequence one bit at a time.

Approach

1. Initialize the result as 0.
2. Iterate 32 times, as the input is a 32-bit integer: - Shift the result left by 1 to make space for the next bit. - Extract the least significant bit of the input number using n & 1 and add it to the result. - Shift the input number right by 1 to process the next bit.
3. After the loop, the result will contain the reversed bits of the input number.
4. Return the result.

Complexity

Time Complexity:

O(1), because we always loop exactly 32 times, regardless of the input.

Space Complexity:

O(1), because we use a constant amount of space.

Code

C++

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        for (int i = 0; i < 32; ++i) {
            result = (result << 1) | (n & 1);
            n >>= 1;
        }
        return result;
    }
};

Python

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for i in range(32):
            result = (result << 1) | (n & 1)
            n >>= 1
        return result

Java

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; ++i) {
            result = (result << 1) | (n & 1);
            n >>= 1;
        }
        return result;
    }
}

JavaScript

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