Reverse Bits

Problem Statement

The task is to reverse the bits of a given 32-bit unsigned integer represented as a binary string. This involves flipping the order of bits from left to right such that the first bit becomes the last one, the second bit becomes the one before the last, and so on, until the last bit becomes the first. This bitwise operation changes the position of all bits in the binary representation of the number while keeping the binary structure intact.

While some programming languages don't support unsigned integers directly (like Java), and use signed types instead, this does not change the binary representation of numbers in our context. The reverse process applies universally to the bit structure, whether the integer is signed or unsigned. The goal is to return the new integer formed by the reversed bits in decimal form accompanied by its new binary representation.

Examples

Example 1

Input:

n = 00000010100101000001111010011100

Output:

964176192 (00111001011110000010100101000000)

Explanation:

The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2

Input:

n = 11111111111111111111111111111101

Output:

3221225471 (10111111111111111111111111111111)

Explanation:

The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Constraints

• The input must be a binary string of length 32

Approach and Intuition

To solve this problem, we can employ a straightforward bit manipulation approach. Here’s a step-by-step breakdown of how our solution would work, taking into consideration the constraints and examples provided:

1. Initialize an empty 32-bit integer for the result where all bits are set to 0. This will store the reversed bits.

2. Iterate 32 times since the input is a 32-bit integer:

   • For each iteration, shift the result to the left by one bit to make room for the next bit to be reversed.

   • Extract the right-most bit from the input using a bitwise AND with 1 (which would be input & 1).

   • Increment the extracted bit to the right-most side of the ongoing result. This can be done using a bitwise OR between the shifted result and the extracted bit.

   • Shift the input right by one to process the next bit during the subsequent iteration.

3. Following the completion of iterations, the result now holds the binary integer that is the reverse of the original input.

This approach moves sequentially through each bit of the input and appropriately adjusts the bits in the result to their reversed positions, ensuring that by the end, the bits are completely reversed respecting their original ordering.

This technique leverages basic bit manipulation operations, such as bitwise AND, OR, and shift operations, which are efficient and commonly supported across different programming languages. The overall time and space complexity of the approach is constant, (O(1)), as it deals with a fixed-size input and uses a bounded number of operations.

Solutions

class Solution {
public:
    uint32_t reverseBits(uint32_t value) {
        value = (value >> 16) | (value << 16);
        value = ((value & 0xff00ff00) >> 8) | ((value & 0x00ff00ff) << 8);
        value = ((value & 0xf0f0f0f0) >> 4) | ((value & 0x0f0f0f0f) << 4);
        value = ((value & 0xcccccccc) >> 2) | ((value & 0x33333333) << 2);
        value = ((value & 0xaaaaaaaa) >> 1) | ((value & 0x55555555) << 1);
        return value;
    }
};