#1009
Complement of Base 10 Integer
Easy Bit masks
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Flip every bit of n's binary form (only the bits that are actually used, no leading zeros) and return the result. For example 5 = 101 becomes 010 = 2.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: flip only the bits that are actually used, not the leading zeros.
Why this works: XOR with a mask of all 1s of the same length flips exactly those bits.
Example: n = 5 (101)
mask grows 1 → 11 → 111101 ^ 111 = 010 → 2
✦Hints open one at a time
~n flips all 32 bits, including the leading zeros — too many.
Build a mask of 1s as long as n's binary form, then XOR.
↗Approach
Grow mask = 1, 11, 111, … until it covers n, then return n ^ mask. Watch the special case n = 0, whose complement is 1.
</>Solution (Java)
class Solution {
public int bitwiseComplement(int n) {
if (n == 0) return 1;
int mask = 0;
while (mask < n) mask = (mask << 1) | 1; // 1, 11, 111, ...
return n ^ mask;
}
}!Common mistake
Returning ~n, which gives a negative number.
Complexity
- Time: O(log n).
- Space: O(1).
