跳转至

476. 数字的补数

题目描述

对整数的二进制表示取反(0110)后,再转换为十进制表示,可以得到这个整数的补数。

  • 例如,整数 5 的二进制表示是 "101" ,取反后得到 "010" ,再转回十进制表示得到补数 2

给你一个整数 num ,输出它的补数。

 

示例 1:

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

示例 2:

输入:num = 1
输出:0
解释:1 的二进制表示为 1(没有前导零位),其补数为 0。所以你需要输出 0 。

 

提示:

  • 1 <= num < 231

 

注意:本题与 1009 https://leetcode.cn/problems/complement-of-base-10-integer/ 相同

解法

方法一:位运算

根据题目描述,我们可以通过异或运算来实现取反的操作,步骤如下:

我们首先找到 $\textit{num}$ 的二进制表示中最高位的 $1$,位置记为 $k$。

然后,构造一个二进制数,第 $k$ 位为 $0$,其余低位为 $1$,即 $2^k - 1$;

最后,将 $\textit{num}$ 与上述构造的二进制数进行异或运算,即可得到答案。

时间复杂度 $O(\log \textit{num})$,其中 $\textit{num}$ 为输入的整数。空间复杂度 $O(1)$。

1
2
3
class Solution:
    def findComplement(self, num: int) -> int:
        return num ^ ((1 << num.bit_length()) - 1)
1
2
3
4
5
class Solution {
    public int findComplement(int num) {
        return num ^ ((1 << (32 - Integer.numberOfLeadingZeros(num))) - 1);
    }
}
1
2
3
4
5
6
class Solution {
public:
    int findComplement(int num) {
        return num ^ ((1LL << (64 - __builtin_clzll(num))) - 1);
    }
};
1
2
3
func findComplement(num int) int {
    return num ^ ((1 << bits.Len(uint(num))) - 1)
}
1
2
3
function findComplement(num: number): number {
    return num ^ (2 ** num.toString(2).length - 1);
}
1
2
3
4
5
6
7
/**
 * @param {number} num
 * @return {number}
 */
var findComplement = function (num) {
    return num ^ (2 ** num.toString(2).length - 1);
};

方法二:位运算(取反+按位与)

1
2
3
function findComplement(num: number): number {
    return ~num & (2 ** num.toString(2).length - 1);
}
1
2
3
4
5
6
7
/**
 * @param {number} num
 * @return {number}
 */
function findComplement(num) {
    return ~num & (2 ** num.toString(2).length - 1);
}

评论