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.
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.
Input: n = 00000010100101000001111010011100
Output: 964176192 (00111001011110000010100101000000)
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).
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.
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.