Reverse Bits - Leetcode Solution

The Reverse Bits problem on LeetCode asks us to reverse the bits of a 32-bit unsigned integer. Let us work through a detailed solution for this problem.

First, let us understand what reversing bits mean. In a binary representation of a number, reversing bits refers to flipping the bits or changing the 0s to 1s and vice versa. For example, the binary representation of the number 43261596 is:

00000010100101000001111010011100

Reversing the bits in this number would give us:

00111001011110000010100101000000

To solve this problem, we can use bit manipulation techniques to iterate through the bits of the input number and reverse them.

We can start by initializing a variable result to zero, as we will start building the reversed bit input from the least significant bit. We can then iterate over all 32 bits of the input number using a for loop. In each iteration, we can shift the input number by i bits to the right and perform a bitwise AND operation with 1. This will give us the value of the i-th bit (starting from the least significant bit). We can then shift the result variable to the left by 1 bit and perform a bitwise OR operation with the value of the i-th bit. This will set the i-th bit of the reversed number to the value of the i-th bit of the input number.

Here is the code implementation of the solution:

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        for (int i = 0; i < 32; i++) {
            result <<= 1; // shift result left by 1 bit
            result |= n & 1; // set least significant bit of result to value of ith bit of n
            n >>= 1; // shift n right by 1 bit to get next bit
        }
        return result;
    }
};

In this solution, we use the uint32_t data type to ensure that we are dealing with 32-bit unsigned integers only. We then initialize the result variable to 0 and use a for loop to iterate over all 32 bits of the input number. Inside the loop, we shift the result variable to the left by one bit and perform a bitwise OR operation with the value of the i-th bit of the input number. Finally, we shift the input number to the right by one bit to get the next bit in the next iteration of the loop.

This solution has a time complexity of O(1) as the number of bits (32) is fixed. The space complexity is also O(1) as we are only using a constant amount of space to store the result variable.

1