Reverse Bits easy

Problem Statement

Reverse bits of a given 32-bit unsigned integer.

For example, if the input is 11111111111111111111111111111101 (which is represented as 4294967293 in decimal), the output should be 10111111111111111111111111111111 (which is represented as 2147483648 in decimal).

Example 1:

Input: n = 43261596 Output: 964176192 Explanation: 43261596 represented in binary as 00000010100101000001111000001000, and reversed is 00010000011110000100101000100000, which is 964176192

Example 2:

Input: n = 0 Output: 0 Explanation: Reversing the bits of 0 will always be 0.

Steps

1. Iterate through bits: We'll iterate through the bits of the input integer from the least significant bit (LSB) to the most significant bit (MSB).
2. Swap bits: For each bit, we'll swap it with the corresponding bit at the opposite end.
3. Build the reversed integer: As we swap bits, we'll construct the reversed integer.

Explanation

The core idea is to systematically swap bits from the beginning and the end of the binary representation of the number. We use bitwise operations to efficiently achieve this. The loop iterates 16 times because we only need to swap pairs of bits; swapping beyond that would just reverse the already-swapped pairs again.

The expression (n >> i) & 1 extracts the i-th bit from the right (LSB side). Similarly, (n << (31 - i)) & 1 extracts the i-th bit from the left (MSB side). The XOR operation is used to swap these bits efficiently.

Code

def reverseBits(n: int) -> int:
    """
    Reverses the bits of a 32-bit unsigned integer.
    """
    result = 0
    for i in range(16):
        # Swap bits i and 31-i
        bit_i = (n >> i) & 1
        bit_31_minus_i = (n >> (31 - i)) & 1
        if bit_i != bit_31_minus_i:
          result |= ((1 << i) | (1 << (31 - i)))
        
    return result

Complexity

• Time Complexity: O(1) - We iterate a fixed number of times (16 iterations). This is constant time because the input size is always 32 bits.
• Space Complexity: O(1) - We use a constant amount of extra space to store variables.