Number Complement

How it works

The complement flips every bit from the least significant bit through the original highest set bit. Keep the original bit-width boundary fixed, then XOR with one mask bit at a time. Leading zero positions above that boundary must remain zero.

Steps

1. Record the original positive value.
2. For each power-of-two mask not exceeding that value, XOR the result.
3. Return the flipped significant bits.

Complexity

• Time: O(log n).
• Space: O(1).

Things to watch for

• Use the original value as the loop bound; the result changes while flipping.
• Do not complement leading zero bits.
• For one, return zero.

class Solution:
    def findComplement(self, num: int) -> int:
        original, mask = num, 1
        while mask <= original:
            num ^= mask
            mask <<= 1
        return num

class Solution {
 public:
  int findComplement(long num) {
    for (long i = 1; i <= num; i <<= 1)
      num ^= i;
    return num;
  }
};