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

Example 2:

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

Steps:

1. Iterate through bits: We iterate through the bits of the input integer n 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 at the opposite end of the integer. This means swapping the i-th bit from the right with the (31-i)-th bit from the right.
3. Accumulate reversed bits: We accumulate the reversed bits into a new integer reversed_n.
4. Bitwise operations: We use bitwise operations (&, |, <<, >>) for efficient manipulation of individual bits.

Explanation:

The core idea is to iteratively swap bits from opposite ends of the 32-bit integer. We use a bitmask and bitwise shifting to isolate and swap individual bits. The loop runs for half the number of bits (16) because swapping beyond that point would just be redundant.

The code efficiently handles the bit manipulation using bitwise operations. The left shift (<<) moves bits to the left, the right shift (>>) moves them to the right, the AND (&) isolates a specific bit, and the OR (|) combines bits.

Code:

uint32_t reverseBits(uint32_t n) {
    uint32_t reversed_n = 0;
    for (int i = 0; i < 16; i++) {
        // Get the i-th bit from the right and (31-i)-th bit from the right
        uint32_t right_bit = (n >> i) & 1;
        uint32_t left_bit = (n >> (31 - i)) & 1;

        // Swap the bits
        reversed_n |= (right_bit << (31 - i));
        reversed_n |= (left_bit << i);
    }
    return reversed_n;
}

Complexity:

• Time Complexity: O(1) - The loop runs a fixed number of times (16 iterations). The operations within the loop are constant time.
• Space Complexity: O(1) - We use a constant amount of extra space to store the reversed_n variable. No additional data structures are needed.