Complement of Base 10 Integer

easy bit manipulation mask xor

Problem

The complement of an integer is obtained by flipping every bit in its binary representation (no leading zeros). Given a non-negative integer n, return its complement. For example, 5 is 101 in binary, whose complement is 010, i.e. 2.

Inputn = 5

Output2

5 = 101₂, flipping each bit gives 010₂ = 2.

n (non-negative)

def bitwise_complement(n):
    mask = 1
    while mask < n:
        mask = (mask << 1) | 1
    return mask ^ n

function bitwiseComplement(n) {
  let mask = 1;
  while (mask < n) {
    mask = (mask << 1) | 1;
  }
  return mask ^ n;
}

class Solution {
    public int bitwiseComplement(int n) {
        int mask = 1;
        while (mask < n) {
            mask = (mask << 1) | 1;
        }
        return mask ^ n;
    }
}

int bitwiseComplement(int n) {
    int mask = 1;
    while (mask < n) {
        mask = (mask << 1) | 1;
    }
    return mask ^ n;
}

Explanation

The complement flips every bit of n — but only the bits that actually make up n, with no leading zeros. The clean way to flip a chosen set of bits is XOR with a mask of all 1s covering exactly those positions.

XOR has the handy property that bit ^ 1 always flips the bit. So if we build a mask that is all 1s and just as wide as n, then mask ^ n flips every bit of n and nothing more.

The loop grows the mask one bit at a time: starting from 1, each step does mask = (mask << 1) | 1, which appends another 1 on the right (so 1 → 11 → 111 → ...). It stops as soon as mask >= n, meaning the mask is now at least as wide as n.

Example: n = 5 is 101. The mask grows to 111 (which is >= 5), and 111 ^ 101 = 010 = 2. So the complement of 5 is 2.

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