Easy

题目描述

整数的补数是将其二进制表示中所有的 0 变为 1，所有的 1 变为 0 后得到的数字。

例如，整数 5 的二进制表示是 “101”，它的补数是 “010”，也就是整数 2。

给你一个整数 num，返回它的补数。

示例 1：

输入：num = 5
输出：2
解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2。

示例 2：

输入：num = 1
输出：0
解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0。

提示：

  • 1 <= num < 2^31

注意： 这个问题与 1009 题相同：https://leetcode.com/problems/complement-of-base-10-integer/

解题思路

解题思路

这道题的核心在于理解"补数"的定义：将二进制表示中的每一位都取反（0变1，1变0）。

有两种主要的解决方案：

方案一：位掩码法（推荐）

关键是找到一个合适的掩码，使得掩码与原数字异或后得到补数。掩码应该是一个长度与原数字二进制位数相同的全1数字。

例如，num = 5 (101)，我们需要的掩码是 111 (7)，这样 5 ^ 7 = 101 ^ 111 = 010 = 2。

方案二：逐位处理法

逐位检查原数字的每一位，如果是1则结果对应位置0，如果是0则结果对应位置1。

推荐使用方案一，因为它利用了位运算的特性，代码更简洁高效。实现时，我们可以通过找到最高位的位置来构造掩码，或者直接计算掩码的值。

具体实现中，我们先找到数字的最高位位置，然后构造一个该位置及以下全为1的掩码，最后与原数字进行异或运算即可得到补数。

代码实现

class Solution {
public:
    int findComplement(int num) {
        // 找到最高位的位置
        int mask = 1;
        int temp = num;
        
        // 构造掩码，使其长度与num的二进制位数相同
        while (temp > 0) {
            mask <<= 1;
            temp >>= 1;
        }
        mask -= 1;
        
        // 异或运算得到补数
        return num ^ mask;
    }
};

class Solution:
    def findComplement(self, num: int) -> int:
        # 计算num的二进制位数
        bit_length = num.bit_length()
        
        # 构造掩码：长度为bit_length的全1数字
        mask = (1 << bit_length) - 1
        
        # 异或运算得到补数
        return num ^ mask

public class Solution {
    public int FindComplement(int num) {
        // 找到最高位的位置
        int mask = 1;
        int temp = num;
        
        // 构造掩码，使其长度与num的二进制位数相同
        while (temp > 0) {
            mask <<= 1;
            temp >>= 1;
        }
        mask -= 1;
        
        // 异或运算得到补数
        return num ^ mask;
    }
}

/**
 * @param {number} num
 * @return {number}
 */
var findComplement = function(num) {
    // 计算num的二进制位数
    const bitLength = num.toString(2).length;
    
    // 构造掩码：长度为bitLength的全1数字
    const mask = (1 << bitLength) - 1;
    
    // 异或运算得到补数
    return num ^ mask;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(log n)
空间复杂度O(1)

其中 n 是输入数字 num 的值。时间复杂度为 O(log n) 是因为需要遍历数字的所有二进制位，空间复杂度为 O(1) 因为只使用了常数个额外变量。