leetcode 2026-03-11 每日一练 - 位运算求补数

题目描述

LeetCode 1009. 位运算求补数

给你一个整数 n，二进制长度固定为 k（即忽略前导零）。

请你计算 n 的补数。

补数定义：将 n 的每一位二进制位取反（0 变 1，1 变 0）得到的数。

示例 1：

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

示例 2：

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

示例 3：

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

解题思路

核心观察

对于一个二进制数 n（假设它的位数为 k），它的补数有一个简洁的数学公式：

补数 = (2^k - 1) - n

其中 2^k - 1 是一个全为 1 的 k 位二进制数（如 7 = 111₂、15 = 1111₂）。

原理图解

以 n = 5 (101₂) 为例：

1
2
3
原码 n:     101
全1数(2^3-1): 111
补数 = 111 - 101 = 010 = 2

所以我们只需要找到大于等于 n 的最小全 1 数，然后减去 n 即可。

算法步骤

  1. 初始化 mask = 1（即 2^0）
  2. 不断将 mask 扩展为 mask = mask * 2 + 1（即 1、3、7、15…）
  3. 当 mask >= n 时停止
  4. 返回 mask - n

代码实现

Go 语言版本

1
2
3
4
5
6
7
8
9
10
11
func bitwiseComplement(n int) int {
    if n == 0 {
        return 1
    }
    
    mask := 1
    for mask < n {
        mask = mask*2 + 1
    }
    return mask - n
}

更简洁的写法

1
2
3
4
5
6
7
func bitwiseComplement(n int) int {
    mask := 1
    for mask < n {
        mask = (mask << 1) | 1
    }
    return mask ^ n
}

或者利用 ^ 异或的性质：

1
2
3
4
5
6
7
8
9
10
11
12
func bitwiseComplement(n int) int {
    if n == 0 {
        return 1
    }
    
    mask := n
    for mask > 0 {
        mask >>= 1
        mask = (mask << 1) | 1
    }
    return mask ^ n
}

C 语言版本

1
2
3
4
5
6
7
8
9
10
11
int bitwiseComplement(int n) {
    if (n == 0) {
        return 1;
    }
    
    int mask = 1;
    while (mask < n) {
        mask = (mask << 1) | 1;
    }
    return mask - n;
}

或者使用异或：

1
2
3
4
5
6
7
int bitwiseComplement(int n) {
    int mask = 1;
    while (mask < n) {
        mask = (mask << 1) | 1;
    }
    return mask ^ n;
}

核心细节

  1. 全 1 数的构造：mask = mask * 2 + 1 每次左移一位并最低位置 1，等价于 mask = (mask << 1) | 1
  2. 边界处理：n = 0 时直接返回 1
  3. 为什么不用按位取反：直接 ^n 会把前导零也取反，结果会多出很多位
  4. 异或替代减法：因为 mask - n = mask ^ n（当 mask 为全 1 时）

复杂度分析

  • 时间复杂度：O(k)，其中 k 是 n 的二进制位数，最多循环约 log₂(n) 次
  • 空间复杂度：O(1)，只使用了常数个变量

示例分析

示例 1：n = 5

  1. mask = 1，1 < 5，继续
  2. mask = 1*2+1 = 3，3 < 5，继续
  3. mask = 3*2+1 = 7，7 >= 5，停止
  4. 返回 7 - 5 = 2

验证：5 (101₂) → 取反 010 (2) ✓

示例 2：n = 7

  1. mask = 1，1 < 7
  2. mask = 3，3 < 7
  3. mask = 7，7 >= 7，停止
  4. 返回 7 - 7 = 0

验证：7 (111₂) → 取反 000 (0) ✓

示例 3：n = 10

  1. mask = 1 → 3 → 7 → 15
  2. 15 >= 10，停止
  3. 返回 15 - 10 = 5

验证：10 (1010₂) → 取反 0101 (5) ✓

边界情况与自测用例

建议覆盖这些测试：

  1. n = 0，答案应为 1（0 → 1）
  2. n = 1，答案应为 0（1 → 0）
  3. n = 2，答案应为 1（10 → 01 = 1）
  4. n = 5，答案应为 2
  5. n = 7，答案应为 0
  6. n = 10，答案应为 5
  7. n = 1024，答案应为 1023

总结

这题的核心在于发现补数的数学本质：

  • 补数 = 全 1 数 - 原数
  • 全 1 数可以通过 2^k - 1 或不断 (x << 1) | 1 构造

理解这个公式后，代码只需几行就能搞定。

参考资料

  • 作者：ylb
  • 链接：https://leetcode.cn/problems/complement-of-base-10-integer/solutions/1377856/
  • 来源：力扣（LeetCode）