### Leetcode: 190. Reverse Bits (Bitwise Operation)

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

# 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!