Reverse Bits easy

Problem Statement

Reverse bits of a given 32-bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000101001010000000).

Example 1:

Input: n = 43261596 Output: 964176192 Explanation: The binary representation of 43261596 is 00000010100101000001111010011100. After reversing the bits, it becomes 00111001011110000101001010000000, which is 964176192.

Example 2:

Input: n = 0 Output: 0 Explanation: Reversing the bits of 0 results in 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: In each iteration, we swap the current bit with the corresponding bit on the other end of the integer. We use bitwise operations to achieve this efficiently.
3. Accumulate the reversed bits: We'll build up the reversed integer bit by bit.

Explanation

The core idea is to use bitwise operations to efficiently manipulate individual bits. We iterate from the least significant bit (rightmost) to the most significant bit (leftmost). In each iteration:

• We extract the least significant bit using the & 1 operation.
• We shift the reversed number to the left by 1 bit (<< 1). This makes space for the new bit.
• We add the extracted bit to the reversed number using the | operation.
• We shift the input number to the right by 1 bit (>> 1), removing the processed least significant bit.

This process continues until all bits have been processed.

Code

function reverseBits(n: number): number {
    let reversed = 0;
    for (let i = 0; i < 32; i++) {
        reversed <<= 1; // Shift reversed number to the left
        reversed |= (n & 1); // Add the least significant bit of n
        n >>= 1; // Shift n to the right
    }
    return reversed >>> 0; // Ensure the result is unsigned
};

Complexity

• Time Complexity: O(1). We iterate a fixed number of times (32 bits).
• Space Complexity: O(1). We use a constant amount of extra space. The space used doesn't scale with the input size.