476. 数字的补数
题目描述
对整数的二进制表示取反(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 < 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 |
|
1 2 3 4 5 |
|
1 2 3 4 5 6 |
|
1 2 3 |
|
1 2 3 |
|
1 2 3 4 5 6 7 |
|
方法二:位运算(取反+按位与)
1 2 3 |
|
1 2 3 4 5 6 7 |
|