Number Complement

easy bit manipulation

Problem

The complement of a positive integer is the number you get by flipping all the bits of its binary representation. Given num, return its complement.

Inputnum = 5

Output2

5 = 101 → flipped 010 = 2. The leading zero bits do not count.

num

def find_complement(num):
    mask = 1
    while mask <= num:
        mask <<= 1
    return (mask - 1) ^ num

function findComplement(num) {
  let mask = 1;
  while (mask <= num) mask <<= 1;
  return (mask - 1) ^ num;
}

class Solution {
    public int findComplement(int num) {
        long mask = 1;
        while (mask <= num) mask <<= 1;
        return (int) ((mask - 1) ^ num);
    }
}

int findComplement(int num) {
    long mask = 1;
    while (mask <= num) mask <<= 1;
    return (int)((mask - 1) ^ num);
}

Explanation

The complement just means flip every bit of the number — but only up to its highest 1 bit. The leading zeros do not count, so we cannot blindly flip a full 32-bit value or we would turn those zeros into ones.

The trick is to build an all-ones mask that is exactly as wide as num. We start at mask = 1 and keep shifting it left (mask <<= 1) until it grows past num. At that point mask is the next power of two, so mask - 1 is a string of ones the same width as num.

Then (mask - 1) ^ num does the flip. XOR with 1 flips a bit, and since every bit of the mask is 1, every bit of num within that width gets flipped.

Example: num = 5 = 101. We grow the mask to 8 = 1000, so mask - 1 = 7 = 111. Then 111 ^ 101 = 010 = 2, the answer.

Because the mask matches the width exactly, only the meaningful bits flip and the leading zeros stay out of the picture.

Time: O(log num) Space: O(1)