Complement of Base 10 Integer
Flip every significant bit — XOR with a mask of "all ones up to the MSB".
2 min read
bit-manipulation
Problem#
Given a non-negative integer n, return its bitwise complement using only the bits up to and including its most-significant set bit.
Examples#
n=5(101) →2(010).n=7(111) →0;n=10(1010) →5(0101).
Constraints#
0 <= n < 10^9.
Approach#
Find the smallest power of two greater than n; subtract one to get a mask of bits up to its MSB; XOR with n.
Solution#
class Solution {public: int bitwiseComplement(int n) { if (n == 0) return 1; unsigned mask = 1; while (mask <= (unsigned)n) mask <<= 1; return (int)((mask - 1) ^ (unsigned)n); }};func bitwiseComplement(n int) int { if n == 0 { return 1 } mask := uint(1) for mask <= uint(n) { mask <<= 1 } return int((mask - 1) ^ uint(n))}class Solution: def bitwiseComplement(self, n: int) -> int: if n == 0: return 1 mask = 1 while mask <= n: mask <<= 1 return (mask - 1) ^ nfunction bitwiseComplement(n) { if (n === 0) return 1; let mask = 1; while (mask <= n) mask <<= 1; return (mask - 1) ^ n;}class Solution { public int bitwiseComplement(int n) { if (n == 0) return 1; long mask = 1; while (mask <= n) mask <<= 1; return (int) ((mask - 1) ^ n); }}function bitwiseComplement(n: number): number { if (n === 0) return 1; let mask = 1; while (mask <= n) mask <<= 1; return (mask - 1) ^ n;}Editorial#
A naked bitwise NOT would flip the upper zero bits too, returning a huge number. The mask covers exactly the significant range; XOR-ing inside it flips each significant bit while leaving the upper bits zero. n == 0 is the corner case — its complement is 1.
Complexity#
- Time:
O(log n). - Space:
O(1).
Concept revision#
Related#