Leetcode 190. Reverse Bits

Problem Explanation

You are given a 32-bit unsigned integer and your task is to reverse its binary form.

For instance, if we consider the binary form of 43261596 is 00000010100101000001111010011100. If we reverse this binary number, we get 00111001011110000010100101000000 which is the binary form of 964176192.

The difficulty arises from the fact that different programming languages handle signed and unsigned integers differently. This should not affect our implementation because the internal binary representation of the integer remains the same whether it is signed or unsigned.

Problem Approach

To solve this problem, we initialize an empty variable ans to 0 and loop through the 32 bits of the input number.

On each iteration, we extract the rightmost bit of the input number and then shift it to the leftmost position in the answer. If the extracted bit is 1, then we add it to the answer.

We then shift the answer to the left to prepare it for the next extracted bit.

Finally, we return the result after all 32 bits have been processed.

Let's consider an example where the input number is 5 (101 in binary) and see how the algorithm works:

• Iteration 1: ans=1, n=2 (10 in binary)
• Iteration 2: ans=10, n=1
• Iteration 3: ans=101, n=0
• ...

In the end, ans has the reversed bits of n.

Python Solution

1
2python
3class Solution:
4    def reverseBits(self, n: int) -> int:
5        ans = 0
6        for _ in range(32):
7            ans = (ans << 1) + (n & 1)
8            n >>= 1
9        return ans

Java Solution

1
2java
3public class Solution {
4    public int reverseBits(int n) {
5        int ans = 0;
6        for (int i = 0; i < 32; i++) {
7            ans = (ans << 1) + (n & 1);
8            n >>= 1;
9        }
10        return ans;
11    }
12}

JavaScript Solution

1
2javascript
3var reverseBits = function(n) {
4    let ans = 0;
5    for (let i = 0; i < 32; i++) {
6        ans = (ans << 1) + (n & 1);
7        n >>= 1;
8    }
9    return ans >>> 0;
10};

C++ Solution

1
2cpp
3class Solution {
4public:
5    uint32_t reverseBits(uint32_t n) {
6        uint32_t ans = 0;
7        for (int i = 0; i < 32; i++) {
8            ans = (ans << 1) + (n & 1);
9            n >>= 1;
10        }
11        return ans;
12    }
13};

C# Solution

1
2csharp
3public class Solution {
4    public uint reverseBits(uint n) {
5        uint ans = 0;
6        for (int i = 0; i < 32; i++) {
7            ans = (ans << 1) + (n & 1);
8            n >>= 1;
9        }
10        return ans;
11    }
12}

In every solution above, we first initialize ans to 0. Then, we loop through 32 bits of n, line (ans << 1) + (n & 1) shifts ans to left and adds rightmost bit of n to ans. Finally, we shift n to the right to prepare for next iteration. When all 32 bits are processed, we return ans. You may note that the solutions provided for each language are quite similar, emphasizing the universality of the binary operations involved. Interestingly, the JavaScript solution includes an extra >>> 0 at the end. This is due to JavaScript's handling of bitwise operations; the bitwise operators convert their operands to signed 32-bit integers, so >>> 0 is used to convert the final result back to an unsigned integer.

It is worth noting that in a professional setting, you would probably use built-in functions that almost every modern language provides. But it's always beneficial to understand how these things work under the hood.

Every one of these solutions have the same time complexity - O(1), as the number of operations is always the same - one for each bit of the number. Similarly, the space complexity is also O(1), as we are only storing two integer variables (n and ans) regardless of the input size.

Keep in mind that this algorithm assumes you are dealing with 32-bit unsigned integers, as this is a common size for integer data types in many languages. However, the algorithm could be easily adapted to handle other bit sizes by modifying the loop to iterate the appropriate number of times.

Whether you're using Python, Java, JavaScript, C++, or C#, the fundamental aspects of bit manipulation remain the same. Understanding these principles can help you tackle a variety of problems in computer science and software engineering, making you a more versatile programmer.