Solution For Reverse Bits

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.

Step by Step Implementation For Reverse Bits

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result += n & 1;
            n >>>= 1;   // CATCH: must do unsigned shift
            if (i < 31) // CATCH: for last digit, don't shift!
                result <<= 1;
        }
        return result;
    }
}

def reverseBits(n): 

result = 0

for i in range(32): 

result <<= 1

result |= n & 1

n >>= 1

return result

var reverseBits = function(n) {
     // convert number to binary string
     let bin = n.toString(2);
     // pad string with zeros so length is 32
     while (bin.length < 32) {
          bin = "0" + bin;
     }
     // reverse string
     bin = bin.split("").reverse().join("");
     // convert reversed string back to number
     return parseInt(bin, 2);
};

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; i < 32; i++) {
            res <<= 1;
            res |= n & 1;
            n >>= 1;
        }
        return res;
    }
};

public class Solution {
    public uint reverseBits(uint n) {
        uint result = 0;
        for (int i = 0; i < 32; i++) {
            result = result << 1;
            result = result | (n & 1);
            n = n >> 1;
        }
        return result;
    }
}

// This solution iterates through the input number one bit at a time, 
// starting with the least significant bit. For each bit, it shifts 
// the result to the left by one bit and ORs it with the input bit.