Complement of Base 10 Integer

Flip every significant bit — XOR with a mask of "all ones up to the MSB".

Easy
Time O(log n) Space O(1)
LeetCode
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#

Complement of Base 10 Integer
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);
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.