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. The reversed binary representation is 00111001011110000101001010000000, which is 964176192.

Example 2

Input: n = 0 Output: 0

Steps

1. Iterate through bits: We iterate through the bits of the input integer n from the least significant bit to the most significant bit.
2. Swap bits: In each iteration, we swap the least significant bit with the most significant bit, the second least significant bit with the second most significant bit, and so on.
3. Build the reversed integer: We build the reversed integer reversed by shifting the bits and applying bitwise OR operations.

Explanation

The solution utilizes bit manipulation techniques to efficiently reverse the bits. We use a loop that iterates 16 times (half the number of bits in a 32-bit integer). In each iteration:

• We extract the least significant bit (n & 1) and the most significant bit (n >>> 31).
• We swap these bits using bitwise operations. We shift the least significant bit to the most significant position ((n & 1) << 31) and the most significant bit to the least significant position ((n >>> 31)).
• We add the swapped bits to our reversed integer using the bitwise OR operator (|=).
• Finally, we right-shift n by 1 (n >>>= 1) to process the next bit. This is an unsigned right shift, crucial to avoid sign extension.

Code

public class ReverseBits {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int reversed = 0;
        for (int i = 0; i < 16; i++) {
            int leastSignificantBit = n & 1;
            int mostSignificantBit = n >>> 31;
            reversed |= (leastSignificantBit << 31 - 2 * i) | (mostSignificantBit << i);
            n >>>= 1;
        }
        return reversed;
    }
}

Complexity

• Time Complexity: O(1) - The loop runs a fixed number of times (16 iterations). It's constant time because it operates on a 32-bit integer.
• Space Complexity: O(1) - The algorithm uses a constant amount of extra space.