Reverse Bits (Leetcode #190)

Reversing bits is a common problem in computer science that allows us to understand how numbers are represented in binary and helps strengthen our bitwise operation skills. In this blog, we'll take a detailed look at the "Reverse Bits" problem from Leetcode and discuss both a brute force approach and an efficient solution. By the end of this post, you should feel more comfortable working with bitwise manipulations, which are crucial in various fields of programming, including cryptography and low-level system design.

Understanding the Problem Statement

The "Reverse Bits" problem asks you to take a given unsigned integer and return its binary representation reversed. For example:

• Input: n = 43261596 (in binary: 00000010100101000001111010011100)

• Output: 964176192 (in binary: 00111001011110000010100101000000)

The problem aims to swap each bit in the original number with the corresponding bit in reverse order.

Brute Force Approach

A common brute force approach to solve this problem is to convert the number to a binary string, pad it to 32 bits (as given in the problem), and reverse the string. This approach looks like:

1. Convert the number to its 32-bit binary representation.

2. Reverse the binary string.

3. Convert the reversed binary string back to an integer.

While this solution works, it's not very efficient, especially given the constraints of bitwise operations. It relies heavily on conversions and string manipulations, which are not ideal when dealing with a large number of computations.

Hint to Solve the Problem Efficiently

To solve this problem efficiently, consider using bitwise operations rather than converting numbers to and from binary strings. Bitwise manipulation provides a more direct and efficient way to solve this problem without unnecessary overhead.

You can iterate through each of the 32 bits, extract the last bit, and shift the result accordingly. This approach allows you to directly manipulate the bits in a single pass.

Efficient Solution

Below, we present the efficient solution for reversing bits, implemented in Python:

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0

        for _ in range(32):
            # Extract the last bit of n
            bit = n & 1

            # Shift result to the left to make space for the extracted bit
            result = (result << 1) | bit

            # Shift n to the right to process the next bit
            n = n >> 1

        return result

This code follows a very direct approach:

1. Initialize result to 0.

2. Iterate through all 32 bits of the input number n.

3. Extract the least significant bit using n & 1.

4. Shift result left by 1 bit and add the extracted bit to result.

5. Shift n right by 1 bit to prepare for extracting the next bit.

6. Finally, return the reversed result.

Time and Space Complexity

Time Complexity: The time complexity of this solution is O(1) because the loop always runs for a fixed number of 32 iterations, irrespective of the input. This makes it very efficient.

Space Complexity: The space complexity is also O(1) since we are only using a constant amount of additional space for the result variable and do not require any extra data structures.

Conclusion

Reversing bits may seem daunting at first, but with bitwise operations, you can solve the problem efficiently and elegantly. Mastering bitwise manipulation opens doors to more efficient code, particularly in areas requiring performance optimization. We encourage you to try different variations of this problem to improve your understanding of bitwise operations.

Feel free to check out the detailed explanation and other problems involving similar bitwise operations on our blog. As always, keep practicing to sharpen your skills!