Leetcode – Reverse Bits Solution in Python

Spread the love

Bit manipulation is an essential tool in a programmer’s arsenal, particularly when optimizing for speed or working with low-level data structures. The Reverse Bits problem on LeetCode is an excellent opportunity to dive into the exciting world of bit manipulation. In this comprehensive article, we will dissect the Reverse Bits problem, explore various algorithms to tackle it, and write Python code for the solutions.

Problem Statement

The Reverse Bits problem is listed as problem number 190 on LeetCode. Here’s the problem statement:

Reverse bits of a given 32 bits unsigned integer.

Example 1:
Input: n = 00000010100101000001111010011100
Output: 964176192 (00111001011110000010100101000000)

Example 2:
Input: n = 11111111111111111111111111111101
Output: 3221225471 (10111111111111111111111111111111)

Understanding the Problem

We are given an unsigned 32-bit integer, and we need to reverse its bits. In other words, if the binary representation of the given integer is b31 b30 ... b1 b0, we need to output an integer with the binary representation b0 b1 ... b30 b31.

Approach 1: Bit by Bit Reversal

One of the most straightforward approaches is to iterate through each bit of the given number and construct the reversed number bit by bit.

To extract the rightmost bit of a number n, we can use the bitwise AND operation: n & 1. To build the reversed number, we can keep adding bits to its right-hand side by shifting the bits to the left and using the bitwise OR operation.

Let’s see how this can be done in Python:

def reverseBits(n):
    result = 0
    for i in range(32):
        # Shift the result to the left to make room for the new bit
        result <<= 1
        # Add the rightmost bit of n to result
        result |= n & 1
        # Shift n to the right to process the next bit
        n >>= 1
    return result

This approach has a time complexity of O(1) because the loop runs a constant number of times (32), and the space complexity is O(1).

Approach 2: Byte by Byte with Caching

An optimization to the bit by bit approach is reversing byte by byte and using a cache to store the reversed bytes. This is more efficient because we can reverse each byte in constant time using a precomputed array and combine them for the final result.

def reverseBits(n):
    # Precompute the reversed bytes
    def reverseByte(byte):
        return (byte * 0x0202020202 & 0x010884422010) % 1023
    
    # Reverse each byte and combine
    result = 0
    for i in range(4):
        result <<= 8
        result |= reverseByte(n & 0xFF)
        n >>= 8
    return result

This approach also has a time complexity of O(1) and a space complexity of O(1).

Approach 3: Bit Swapping

Another approach is to swap corresponding bits in the number. Specifically, swap the ith bit from the right with the ith bit from the left.

def reverseBits(n):
    result = 0
    for i in range(32):
        # Isolate the ith bit from the right
        bit = (n >> i) & 1
        # Move the bit to the correct position and add to result
        result |= bit << (31 - i)
    return result

Like the previous approaches, this one also has a time complexity of O(1) and a space complexity of O(1).

Practical Implications

Bit manipulation is especially significant in embedded systems, cryptography, network protocols, and error detection/correction algorithms. Understanding bit-level operations is crucial for optimizing code for performance and resource usage, which can be critical in systems with limited computing power or memory.

Conclusion

The Reverse Bits problem serves as an introduction to the powerful and often underappreciated domain of bit manipulation. We have seen three different algorithms to solve this problem, which although they all have similar time and space complexities, offer different insights into working with bits. Gaining a deep understanding of bit manipulation is indispensable for any programmer seeking to write high-performance code or work with low-level data structures.

Leave a Reply