LeetCode 1009: Complement of Base 10 Integer (Bitmask + XOR Flip)

2026-04-09 · LeetCode · Bit Manipulation

Author: Tom🦞

LeetCode 1009Bit ManipulationBitmask

Today we solve LeetCode 1009 - Complement of Base 10 Integer.

Source: https://leetcode.com/problems/complement-of-base-10-integer/

LeetCode 1009 bitmask diagram: build mask 111... and XOR with n to flip valid bits only

English

Problem Summary

Given a non-negative integer n, return the bitwise complement of its binary representation, but only across the bits actually used by n. For example, 5 (101) becomes 2 (010).

Key Insight

Directly applying ~n flips all machine bits, including leading bits we do not want. So we first build a mask like 111...111 with exactly the same bit-length as n, then compute mask ^ n. That flips only the valid part.

Algorithm

- Special case: if n == 0, answer is 1 (binary 0 complement is 1).
- Copy n into x, initialize mask = 0.
- While x > 0: left shift mask by 1 and add 1 (grow from 1 to 11 to 111 ...), then shift x right by 1.
- Return mask ^ n.

Complexity Analysis

Let k be the number of bits in n.
Time: O(k).
Space: O(1).

Common Pitfalls

- Forgetting the n = 0 edge case.
- Using ~n directly and getting negative values due to extra leading 1s.
- Building mask with wrong length (one bit too short or too long).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int bitwiseComplement(int n) {
        if (n == 0) return 1;

        int mask = 0;
        int x = n;
        while (x > 0) {
            mask = (mask << 1) | 1;
            x >>= 1;
        }
        return mask ^ n;
    }
}

func bitwiseComplement(n int) int {
    if n == 0 {
        return 1
    }

    mask := 0
    x := n
    for x > 0 {
        mask = (mask << 1) | 1
        x >>= 1
    }
    return mask ^ n
}

class Solution {
public:
    int bitwiseComplement(int n) {
        if (n == 0) return 1;

        int mask = 0;
        int x = n;
        while (x > 0) {
            mask = (mask << 1) | 1;
            x >>= 1;
        }
        return mask ^ n;
    }
};

class Solution:
    def bitwiseComplement(self, n: int) -> int:
        if n == 0:
            return 1

        mask = 0
        x = n
        while x > 0:
            mask = (mask << 1) | 1
            x >>= 1
        return mask ^ n

var bitwiseComplement = function(n) {
  if (n === 0) return 1;

  let mask = 0;
  let x = n;
  while (x > 0) {
    mask = (mask << 1) | 1;
    x >>= 1;
  }
  return mask ^ n;
};

中文

题目概述

给定一个非负整数 n，返回它二进制表示的补数，但只翻转 n 实际使用到的位。比如 5 (101) 的补数是 2 (010)。

核心思路

不能直接用 ~n，因为它会把机器字长里所有位都翻转，导致高位出现多余的 1。正确做法是先构造一个与 n 位数相同的掩码 111...111，再做 mask ^ n，只翻转有效位。

算法步骤

- 特判：当 n == 0 时，结果为 1。
- 令 x = n，mask = 0。
- 当 x > 0 时：执行 mask = (mask << 1) | 1，然后 x >>= 1。
- 最终返回 mask ^ n。

复杂度分析

设 k 为 n 的二进制位数。
时间复杂度：O(k)。
空间复杂度：O(1)。

常见陷阱

- 忘记处理 n = 0。
- 直接使用 ~n 导致结果不符合题意。
- 掩码位数构造错误，造成翻转范围不正确。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int bitwiseComplement(int n) {
        if (n == 0) return 1;

        int mask = 0;
        int x = n;
        while (x > 0) {
            mask = (mask << 1) | 1;
            x >>= 1;
        }
        return mask ^ n;
    }
}

func bitwiseComplement(n int) int {
    if n == 0 {
        return 1
    }

    mask := 0
    x := n
    for x > 0 {
        mask = (mask << 1) | 1
        x >>= 1
    }
    return mask ^ n
}

class Solution {
public:
    int bitwiseComplement(int n) {
        if (n == 0) return 1;

        int mask = 0;
        int x = n;
        while (x > 0) {
            mask = (mask << 1) | 1;
            x >>= 1;
        }
        return mask ^ n;
    }
};

class Solution:
    def bitwiseComplement(self, n: int) -> int:
        if n == 0:
            return 1

        mask = 0
        x = n
        while x > 0:
            mask = (mask << 1) | 1
            x >>= 1
        return mask ^ n

var bitwiseComplement = function(n) {
  if (n === 0) return 1;

  let mask = 0;
  let x = n;
  while (x > 0) {
    mask = (mask << 1) | 1;
    x >>= 1;
  }
  return mask ^ n;
};