Easy

题目描述

整数的反码是通过翻转其二进制表示中所有的 0 变为 1，所有的 1 变为 0 而得到的整数。

例如，整数 5 的二进制表示是 “101”，其反码是 “010”，即整数 2。

给定一个整数 n，返回其反码。

示例 1：

输入：n = 5
输出：2
解释：5 的二进制表示为 "101"，反码为 "010"，即十进制的 2。

示例 2：

输入：n = 7
输出：0
解释：7 的二进制表示为 "111"，反码为 "000"，即十进制的 0。

示例 3：

输入：n = 10
输出：5
解释：10 的二进制表示为 "1010"，反码为 "0101"，即十进制的 5。

约束条件：

  • 0 <= n < 10^9

注意： 此题与 476 题相同。

提示：

  • 一个二进制数加上它的反码等于 111….111（全1）。同时，N = 0 是一个特殊情况。

解题思路

这道题要求计算一个数的二进制反码。关键在于理解什么是"反码"以及如何高效地计算。

核心思路：

反码就是将数字的二进制表示中的每一位取反。但需要注意的是，我们只对有效位进行取反，而不是对所有32位都取反。

解法分析：

  1. 特殊情况处理：当 n = 0 时，其二进制为 “0”，反码为 “1”，结果应该是 1。

  2. 构造掩码法（推荐）：

    • 首先找到 n 的二进制表示中最高位的位置
    • 构造一个掩码，该掩码的低位部分全为 1，位数等于 n 的有效位数
    • 使用 XOR 运算得到反码：mask ^ n

  3. 位操作实现：

    • 可以通过不断左移 1 来构造掩码，直到掩码大于 n
    • 或者通过计算 n 的位长度来直接构造掩码

算法步骤：

  1. 处理特殊情况 n = 0
  2. 找到大于 n 的最小的形如 (1111…1) 的数作为掩码
  3. 返回 mask ^ n 作为结果

这种方法时间复杂度低，代码简洁，是最优解法。

代码实现

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

class Solution:
    def bitwiseComplement(self, n: int) -> int:
        if n == 0:
            return 1
        
        mask = 1
        while mask < n:
            mask = (mask << 1) | 1
        
        return mask ^ n

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

/**
 * @param {number} n
 * @return {number}
 */
var bitwiseComplement = function(n) {
    if (n === 0) return 1;
    
    let bitLength = Math.floor(Math.log2(n)) + 1;
    let mask = (1 << bitLength) - 1;
    
    return n ^ mask;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(log n)需要找到 n 的最高位，循环次数为 log₂(n)
空间复杂度O(1)只使用常数额外空间