Reverse Bits - Video Solutions
Reverse Bits - Binary - Leetcode 190 - Python
Reverse Bits - Video Solution
Watch 10 video solutions for Reverse Bits, a easy level problem involving Divide and Conquer, Bit Manipulation. This walkthrough by NeetCode has 189,756 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Reverse bits of a given 32 bits unsigned integer.
Note:
- Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
- In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above, the input represents the signed integer
-3and 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:
- The input must be a binary string of length
32
Follow up: If this function is called many times, how would you optimize it?
Approach Overview
Problem Overview: You are given a 32-bit unsigned integer and must reverse its binary representation. The least significant bit becomes the most significant bit, the second least becomes the second most, and so on. The result is another 32-bit integer formed from this reversed bit order.
Approach 1: Bitwise Shift and OR (Time: O(32), Space: O(1))
This method builds the reversed number one bit at a time. Iterate through all 32 bits of the input integer. At each step, extract the last bit using n & 1, shift the result left by one position, and append the extracted bit using a bitwise OR. Then shift the original number right using n >> 1. After 32 iterations, the constructed number contains the reversed bit order. This approach relies purely on basic bit manipulation operations and is easy to implement in any language.
The key idea is treating the integer as a stream of bits. Each iteration pulls the least significant bit and pushes it into the reversed result from the left side. Because a 32-bit integer always has a fixed width, the loop runs exactly 32 times, making the algorithm effectively constant time. This is the most common solution used in interviews and coding platforms.
Approach 2: Bit Manipulation with Precomputed Masks (Time: O(1), Space: O(1))
This approach reverses bits in groups instead of processing them one by one. It uses precomputed bit masks to swap halves, then quarters, then smaller groups of bits. For example, swap the left and right 16-bit halves, then swap 8-bit groups, then 4-bit groups, and continue until single bits are swapped. Each stage uses masks and shifts such as (n & mask) << k and (n >> k) & mask to reposition groups of bits.
The idea follows a divide and conquer pattern. Instead of reversing sequentially, the algorithm repeatedly splits the integer into smaller segments and swaps them using bit masks. Because the number of operations is fixed and independent of input value, the complexity is constant time. This technique appears frequently in systems programming and performance-critical bit operations.
Recommended for interviews: The shift-and-OR approach is what most interviewers expect. It demonstrates clear understanding of bit manipulation fundamentals such as masking, shifting, and constructing integers bit by bit. The mask-based divide-and-conquer technique is more advanced and useful when discussing optimized bit tricks or low-level performance.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bitwise Shift and OR | O(32) | O(1) | General solution for interviews and coding platforms; easy to understand and implement |
| Bit Manipulation with Precomputed Masks | O(1) | O(1) | When optimizing bit operations or demonstrating advanced bit tricks |