Reverse bits of a given 32 bits unsigned integer.
Note:
-3 and the output represents the signed integer -1073741825.Example 1:
Input: n = 00000010100101000001111010011100 Output: 964176192 (00111001011110000010100101000000) Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:
Input: n = 11111111111111111111111111111101 Output: 3221225471 (10111111111111111111111111111111) Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.
Constraints:
32Follow up: If this function is called many times, how would you optimize it?
The goal of #190 Reverse Bits is to reverse the order of bits in a 32-bit unsigned integer. A straightforward approach is to process the number bit by bit. Repeatedly extract the least significant bit using a bit operation like n & 1, shift the result to the left, and then shift the original number to the right. This effectively rebuilds the number in reverse bit order.
Another optimized idea uses a divide and conquer strategy with bit masks. Instead of reversing one bit at a time, groups of bits (such as 1-bit, 2-bit, 4-bit, 8-bit blocks, etc.) are swapped using masks and shift operations. This technique reduces the number of operations and is commonly used in performance-sensitive scenarios.
Since the input size is fixed at 32 bits, the process always runs in constant time. The problem mainly tests understanding of bit manipulation, shifting, and masking operations.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bit-by-bit reversal | O(1) (32 iterations) | O(1) |
| Divide and conquer with bit masks | O(1) | O(1) |
NeetCode
In this approach, we utilize bitwise operations to reverse the bits. We iterate through each bit of the number from the least significant bit (LSB) to the most significant bit (MSB), shifting the resultant bits to the left and using the bitwise OR operation to set the bits in the reversed order.
Time Complexity: O(1) because the operation involves a fixed number of 32 iterations, and each operation within the loop is O(1).
Space Complexity: O(1) since we only use a constant amount of additional space for variables.
1public class Solution {
2 public int reverseBits(int n) {
3 int result = 0;
4 for (int i =This Java implementation uses a similar approach with the difference in using '>>>' for unsigned right shift, as Java doesn't have an unsigned int type.
This approach could be optimized by precomputing masks that handle groups of bits. This reduces the need for iterating through each bit and instead processes larger chunks of bits through bit manipulation techniques.
Time Complexity: O(1).
Space Complexity: O(1).
1public class Solution {
2 public uint reverseBits(uint n) {
n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1);
n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2);
n = ((n >> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4);
n = ((n >> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8);
n = ((n >> 16) & 0x0000FFFF) | ((n & 0x0000FFFF) << 16);
return n;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, bit manipulation questions like Reverse Bits frequently appear in technical interviews, including FAANG companies. They test a candidate's understanding of low-level operations, efficiency, and familiarity with binary representations.
The common optimal approach processes the number bit by bit while shifting the result left and the input right. Since the integer is limited to 32 bits, the algorithm runs in constant time. An alternative uses divide-and-conquer bit masks to swap groups of bits efficiently.
Bit manipulation allows direct access to individual bits of an integer. By using operations like AND, OR, and shifts, you can extract, move, and rebuild bits efficiently, which is exactly what is needed to reverse their order.
No complex data structure is required for this problem. It relies purely on bit manipulation operations such as shifts and masks. Understanding how to extract and reposition bits is the key concept.
This C# approach uses precomputed masks for reversing bits, performing fewer operations to produce the reversed value efficiently, particularly valuable when the function is called numerous times.