#算法#位运算#leetcode

整数的补数：位运算掩码解法

LeetCode 476 题，用掩码 XOR 实现整数补数，附 C++/Python/Java 三种实现及补数与补码的区别

$⏱1.4k 字/约 6 min👁— views

整数的补数：位运算掩码解法

LeetCode 476 号题"数字的补数"（Number Complement）是一道经典的位运算题，看似简单，却能引出多种思路和技巧。本文从朴素解法到位运算优化，逐步推导，并给出 Python、C++、JavaScript 三语言实现。

题目描述

给你一个正整数 num，输出它的补数。补数是对该数的二进制表示取反（仅对有效位取反，不包含前导零）。

示例：

输入：num = 5
输出：2
解释：5 的二进制是 101，取反得 010，即 2

输入：num = 1
输出：0
解释：1 的二进制是 1，取反得 0

输入：num = 7
输出：0
解释：7 的二进制是 111，取反得 000，即 0

输入：num = 10
输出：5
解释：10 的二进制是 1010，取反得 0101，即 5

约束：1 <= num < 2^31

朴素解法

最直观的方法：逐位取反。

def findComplement_naive(num: int) -> int:
    # 找到最高有效位的位置
    bit = 1
    temp = num
    result = 0
    pos = 0
    
    while temp > 0:
        # 取当前最低位，取反后放到结果对应位置
        current_bit = temp & 1
        flipped = 1 - current_bit  # 0变1，1变0
        result |= (flipped << pos)
        temp >>= 1
        pos += 1
    
    return result

时间复杂度 O(log n)，空间复杂度 O(1)。

位运算思路推导

核心思想：XOR 取反

对二进制数取反，等价于与全 1 掩码进行 XOR 运算：

  101  (5)
XOR
  111  (mask = 全1)
= 010  (2，即结果)

问题转化为：如何构造一个与 num 等长的"全 1 掩码"？

掩码的含义

如果 num 有 k 位有效位，那么掩码 mask = 2^k - 1，即 k 个 1。

num = 5 = 0b101  （3 位）
mask    = 0b111  = 2^3 - 1 = 7
result  = 5 XOR 7 = 2

num = 10 = 0b1010  （4 位）
mask     = 0b1111  = 2^4 - 1 = 15
result   = 10 XOR 15 = 5

掩码生成的三种方法

方法一：循环移位

def get_mask_loop(num: int) -> int:
    mask = 1
    while mask <= num:
        mask <<= 1
    return mask - 1

解析：

  • 从 mask = 1 开始，不断左移
  • 当 mask > num 时，mask 是 2^k（比 num 多一位）
  • mask - 1 就是 k 个 1 组成的掩码
num = 5 (0b101):
mask 迭代: 1 → 2 → 4 → 8 (8 > 5, 停止)
mask - 1 = 7 = 0b111  ✓

方法二：bit_length()

Python 的整数有 bit_length() 方法，返回二进制表示的有效位数：

def get_mask_bitlength(num: int) -> int:
    k = num.bit_length()  # 有效位数
    return (1 << k) - 1   # 2^k - 1

5.bit_length() = 3
(1 << 3) - 1 = 8 - 1 = 7 = 0b111  ✓

这是 Python 中最简洁的方法。

方法三：log2 计算

import math

def get_mask_log(num: int) -> int:
    k = math.floor(math.log2(num)) + 1  # 位数
    return (1 << k) - 1

注意：浮点数精度问题可能导致 math.log2 在某些特殊值（如 2^k）时返回不准确的结果，推荐使用 bit_length() 代替。

# 安全版本（避免浮点问题）
def get_mask_safe(num: int) -> int:
    k = int(math.log2(num)) + 1
    # 验证并修正
    if (1 << (k-1)) > num:
        k -= 1
    return (1 << k) - 1

完整解法

Python

class Solution:
    def findComplement(self, num: int) -> int:
        # 方法一：位移构造掩码
        mask = 1
        while mask <= num:
            mask <<= 1
        return (mask - 1) ^ num
    
    # 方法二：bit_length（更Pythonic）
    def findComplement_v2(self, num: int) -> int:
        return ((1 << num.bit_length()) - 1) ^ num
    
    # 方法三：一行版本
    def findComplement_v3(self, num: int) -> int:
        return num ^ (2 ** num.bit_length() - 1)

C++

class Solution {
public:
    int findComplement(int num) {
        // 构造掩码（使用 unsigned 避免溢出）
        unsigned int mask = 1;
        while (mask <= (unsigned int)num) {
            mask <<= 1;
        }
        return (mask - 1) ^ num;
    }
    
    // 使用内置函数（GCC）
    int findComplement_v2(int num) {
        // __builtin_clz 计算前导零数
        // 32 位整数总位数 - 前导零数 = 有效位数
        int k = 32 - __builtin_clz(num);
        // 构造 k 个 1 的掩码
        // 注意：当 k=32 时，(1 << 32) 会溢出，需要特殊处理
        if (k == 32) return ~num;
        int mask = (1 << k) - 1;
        return mask ^ num;
    }
    
    // 更安全的版本（使用 long long 避免溢出）
    int findComplement_v3(int num) {
        long long mask = 1;
        while (mask <= num) {
            mask <<= 1;
        }
        return (int)((mask - 1) ^ num);
    }
};

注意 C++ 中的溢出风险：

  • int 是有符号 32 位，左移到第 31 位会触发未定义行为
  • 使用 unsigned int 或 long long 更安全

JavaScript

/**
 * @param {number} num
 * @return {number}
 */
var findComplement = function(num) {
    // JavaScript 的位运算基于 32 位有符号整数
    let mask = 1;
    while (mask <= num) {
        mask <<= 1;
    }
    return (mask - 1) ^ num;
};

// 使用 Math.clz32（计算 32 位前导零）
var findComplement_v2 = function(num) {
    const k = 32 - Math.clz32(num);
    const mask = (1 << k) - 1;
    return mask ^ num;
};

// 注意：JavaScript 的位运算只支持 32 位整数
// 对于 num >= 2^30 时，(1 << k) 可能出现符号位问题
// 使用 >>>0 转为无符号
var findComplement_safe = function(num) {
    let mask = 1;
    while ((mask >>> 0) <= (num >>> 0)) {
        mask = (mask << 1) >>> 0;
    }
    return ((mask - 1) ^ num) >>> 0;
};

复杂度分析

所有方法的复杂度均为：

  • 时间复杂度：O(log n)——需要处理 num 的每一位
  • 空间复杂度：O(1)——仅使用常数个变量

实际上，bit_length() / __builtin_clz 是 O(1) 的硬件指令级操作，在这道题中完全等价，但概念上更接近 O(log n)。

相关题目延伸

LeetCode 461：汉明距离

汉明距离 = 两个整数 XOR 后 1 的个数：

def hammingDistance(x, y):
    return bin(x ^ y).count('1')

LeetCode 191：位 1 的个数（汉明重量）

def hammingWeight(n):
    return bin(n).count('1')
    # 或用 Brian Kernighan 算法
    count = 0
    while n:
        n &= n - 1  # 清除最低位的 1
        count += 1
    return count

LeetCode 338：比特位计数

def countBits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

延伸思考：负数的补码

本题的"补数"（complement）与计算机底层的"补码"（two’s complement）不同：

  • 本题补数 = 对有效位取反（无符号视角）
  • 补码 = 取反 + 1（有符号表示负数的方式）

区分清楚这两个概念，有助于理解更复杂的位运算题。

掌握了掩码构造技巧后，遇到类似的"对有效位操作"的题目，都可以套用这个思路。