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 00111001011110000100101010000010).

Example 1

Input: n = 43261596 Output: 964176192 Explanation: The binary representation of 43261596 is 00000010100101000001111010011100. The binary representation of 964176192 is 00111001011110000100101010000010.

Example 2

Input: n = 0 Output: 0 Explanation: The binary representation of 0 is 0.

Steps

  1. Iterate through bits: We'll iterate through the bits of the input integer from least significant bit (LSB) to most significant bit (MSB).

  2. Swap bits: In each iteration, we'll swap the current bit (from the LSB) with the corresponding bit from the MSB.

  3. Bit manipulation: We'll use bitwise operators (&, |, >>, <<) to extract, shift, and combine bits efficiently.

  4. Build reversed integer: We'll build the reversed integer bit by bit.

Explanation

The core idea is to swap bits symmetrically from the left and right ends of the 32-bit integer. We use a loop to iterate through half the bits (16 iterations are sufficient because we're swapping pairs). In each iteration:

  • We extract the least significant bit (LSB) using a bitwise AND (& 1).
  • We extract the most significant bit (MSB) using a right shift (>> 31). Note that for a 32-bit integer, shifting 31 bits to the right puts the MSB in the LSB position.
  • We swap the bits by applying bitwise XOR (^) to toggle them if necessary. If the LSB and MSB are different, this will effectively swap them. If they are the same, it does nothing.
  • We shift the result to the left and the original number to the right, preparing for the next iteration.

Code

public class Solution {
    public uint reverseBits(uint n) {
        uint result = 0;
        for (int i = 0; i < 16; i++) {
            uint lsb = n & 1;
            uint msb = n >> 31;
            result |= (lsb << (31 - 2 * i)); //Place LSB in its reversed position
            result |= (msb << i); //Place MSB in its reversed position

            n >>=1; //shift right by 1
            n &= ~(1 << 31); //clear MSB to avoid shifting in 1's
        }
        return result;
    }
}

Complexity

  • Time Complexity: O(1) - We perform a fixed number of operations (32 bit shifts and operations).
  • Space Complexity: O(1) - We use a constant amount of extra space.