Reverse Bits

Mark as Completed

Lesson

Write a function that takes a 32-bit unsigned integer as input and returns the integer with its bits reversed. For example, if the input integer is 10, which is represented in binary as 1010, the function should return 5, which is represented in binary as 0101.

For example:

reverseBits(10); // Expected output: 5

Walkthrough

To solve this problem, we can use bitwise operations to reverse the bits of the input number. We will use a loop to traverse through each bit of the input number from the right to the left. For each bit, we will perform a left shift on the result variable, then perform a bitwise OR with the current bit of the input number. We will then perform a bitwise right shift on the input number to move to the next bit. Once we have reversed all the bits, we will return the result.

Here is the implementation of the reverseBits
function:

const reverseBits = (n) => {
    let result = 0;
    for (let i = 0; i < 32; i++) {
        result <<= 1;
        result |= n & 1;
        n >>= 1;
    }
    return result >>> 0;
};

In the above implementation, we initialize the result
variable to 0, which will store the reversed bits of the input number. We then use a loop to traverse through each bit of the input number from the right to the left. In each iteration of the loop, we perform a left shift on the result
variable by 1 bit using the <<
operator. This moves all the bits of the result
variable one position to the left, making room for the current bit of the input number. We then perform a bitwise OR with the current bit of the input number using the |
operator. This sets the corresponding bit of the result
variable to the same value as the current bit of the input number. Finally, we perform a bitwise right shift on the input number using the >>
operator to move to the next bit.Once we have reversed all the bits of the input number, we return the result
variable. The >>>
operator is used to convert the signed integer to an unsigned integer, since the result may have a leading 1 bit that would cause it to be interpreted as a negative number.

Big O Complexity Analysis:

The time complexity of this solution is O(32) or O(1), since we always perform 32 bitwise operations on the input number, which has a fixed size of 32 bits. The space complexity of this solution is also O(1), since we only use a single integer variable to store the reversed bits of the input number.

Previous Lesson Next Lesson