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:
32
Follow up: If this function is called many times, how would you optimize it?
Problem Overview: You are given a 32-bit unsigned integer and need to reverse its binary representation. The least significant bit becomes the most significant bit, the second least significant becomes the second most significant, and so on. The result is another 32-bit integer with the bit order flipped.
Approach 1: Bitwise Shift and OR (O(32) time, O(1) space)
This approach builds the reversed number one bit at a time using basic bit manipulation. Iterate through all 32 bits of the input number. At each step, extract the last bit using n & 1, shift the result left by one position, and insert the extracted bit using a bitwise OR. Then shift the input number right by one position to process the next bit. After 32 iterations, the result contains the reversed bit pattern. This method is straightforward, easy to reason about, and commonly expected in interviews because it demonstrates a clear understanding of bitwise operations.
Approach 2: Bit Manipulation with Precomputed Masks (O(1) time, O(1) space)
This optimized technique reverses bits in groups instead of processing them one by one. Using precomputed bit masks, you repeatedly swap halves of the number: first 16-bit halves, then 8-bit blocks, then 4-bit groups, followed by 2-bit and 1-bit swaps. Each step uses masks and bit shifts to isolate sections of the integer and reposition them. Conceptually, this resembles a divide and conquer strategy applied at the bit level, where the number is progressively rearranged into its reversed form. Since the number of operations is fixed, the runtime is constant and extremely fast in performance-critical systems.
Recommended for interviews: The bitwise shift and OR approach is usually what interviewers expect first. It clearly shows you understand how to extract bits, shift values, and reconstruct numbers using bit operations. The mask-based approach demonstrates deeper knowledge of low-level optimization and is often used in systems programming or libraries where reversing bits must be done repeatedly with minimal overhead.
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.
The function takes an unsigned integer and iteratively reverses its bits. It starts with a result initialized to 0. For each bit, the result is shifted left, and the last bit of 'n' is added using the bitwise OR operation. 'n' is then shifted right by one to process the next bit. This ensures that the bits from 'n' are reversed and stored in the result.
C++
Java
Python
C#
JavaScript
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.
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.
This solution involves swapping bits in progressively larger chunks. It uses binary masks (e.g., 0x55555555, 0x33333333) to select and swap specific bits. This method is efficient as it reduces the number of operations required, making it faster for multiple invocations.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1).
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Bitwise Shift and OR | Time Complexity: O(1) because the operation involves a fixed number of 32 iterations, and each operation within the loop is O(1). |
| Approach 2: Bit Manipulation with Precomputed Masks | Time Complexity: O(1). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bitwise Shift and OR | O(32) | O(1) | Best for interviews and general understanding of bit manipulation |
| Bit Manipulation with Precomputed Masks | O(1) | O(1) | When reversing bits frequently or optimizing low-level performance |
Reverse Bits - Binary - Leetcode 190 - Python • NeetCode • 146,967 views views
Watch 9 more video solutions →Practice Reverse Bits with our built-in code editor and test cases.
Practice on FleetCode