190. Reverse Bits
Approach
Bit-by-bit extraction and reassembly over exactly 32 iterations.
At each step: left-shift the result to make room, extract the LSB of n (n & 1), OR it into result.
Right-shift n to expose the next bit.
After 32 iterations the 32 bits of n appear in reverse order in the result.
Using uint avoids sign-extension issues that would occur with int right shifts.
Key Techniques
Bit manipulation uses bitwise operators (&, |, ^, ~, <<, >>) for compact and fast solutions. Key tricks: x & (x-1) clears lowest set bit, x ^ x = 0 (XOR cancellation), and bitmask DP represents subsets as integers. In C#, use int (32-bit) or long (64-bit) for bitmasking.
Divide and conquer splits a problem into independent sub-problems, solves each recursively, and combines the results. Classic examples: merge sort, quick sort, binary search, and closest pair of points. Master Theorem helps analyze time complexity: T(n) = aT(n/b) + f(n).
// Approach: Bit-by-bit extraction and reassembly over exactly 32 iterations.
// At each step: left-shift the result to make room, extract the LSB of n (n & 1), OR it into result.
// Right-shift n to expose the next bit.
// After 32 iterations the 32 bits of n appear in reverse order in the result.
// Using uint avoids sign-extension issues that would occur with int right shifts.
// Time: O(1) — always exactly 32 iterations. Space: O(1).
public class Solution
{
public uint ReverseBits(uint n)
{
uint ans = 0;
for (int i = 0; i < 32; i++)
{
ans <<= 1;
if ((n & 1) == 1)
ans += 1;
n >>= 1;
}
return ans;
}
}
public class Solution1
{
public int ReverseBits(int n)
{
int ans = 0;
for (int i = 0; i < 32; i++)
{
ans <<= 1;
if ((n & 1) == 1)
ans += 1;
n >>= 1;
}
return ans;
}
}