Leetcode: 190. Reverse Bits (Bitwise Operation)

Reversing Bits of a 32-Bit Unsigned Integer in C++

Introduction: In this blog post, we'll explore a simple C++ solution to reverse the bits of a given 32-bit unsigned integer. The task is to reverse the binary representation of the input integer, producing a new integer with its bits flipped in the opposite order. Understanding how to efficiently reverse bits can be beneficial in various scenarios, such as in low-level programming or bit manipulation tasks.

Problem Description: The problem can be stated as follows: Given a 32-bit unsigned integer n, we need to reverse its bits and return the resulting integer. The reversal involves flipping the order of bits from left to right and vice versa.

Approach: To solve this problem, we will implement a function called reverseBits, which takes an unsigned 32-bit integer n as input and returns the integer with its bits reversed.

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ret = 0, power = 31;
        while (n != 0) {
            ret += (n & 1) << power;
            n = n >> 1;
            power -= 1;
        }
        return ret;
    }
};

Explanation: Let's break down the implementation step by step:

1. We initialize two variables, ret and power. ret will hold the resulting reversed integer, and power is used as a power of 2 to set the appropriate bit positions while reversing.
2. The while loop runs until the input integer n becomes 0, indicating that all its bits have been processed.
3. Within the loop, we use bitwise AND (&) with 1 to extract the least significant bit of n. We then left-shift this extracted bit by the value of power, effectively setting the bit in the reversed integer at the corresponding position.
4. Next, we right-shift n by 1, effectively moving to the next bit in the original integer.
5. We decrement power by 1, ensuring that the next bit in the reversed integer is set in the appropriate position.
6. The loop continues this process until all bits of n have been processed, and power becomes 0.
7. Finally, we return the reversed integer ret as the result.

Example: Let's illustrate the implementation with an example. Consider the input number 43261596 (represented as 00000010100101000001111010011100 in binary):

1. Initially, ret = 0 and power = 31.
2. For the first bit (0) in the input, ret = 0 + (0 & 1) << 31 = 0 (No change in ret).
3. For the second bit (0) in the input, ret = 0 + (0 & 1) << 30 = 0 (No change in ret).
4. For the third bit (1) in the input, ret = 0 + (1 & 1) << 29 = 01000000000000000000000000000000.
5. For the fourth bit (1) in the input, ret = 01000000000000000000000000000000 + (1 & 1) << 28 = 01100000000000000000000000000000.
6. And so on, we continue the process until all bits are processed.

So, the reversed integer is 964176192 (represented as 00111001011110000010100101000000 in binary).

Conclusion: We have successfully implemented a C++ solution to reverse the bits of a given 32-bit unsigned integer. The provided function, reverseBits, efficiently performs the bit reversal in linear time complexity. Understanding this bit manipulation technique can prove useful in various low-level programming tasks. Whether you're working on embedded systems or optimizing algorithms that involve bit operations, this knowledge can be invaluable. Happy coding!