0476-数字的补数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

对整数的二进制表示取反（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.com/problems/complement-of-
base-10-integer/> 相同

方法一：位运算

思路与算法

根据题目的要求，我们需要将 num 二进制表示的每一位取反。然而在计算机存储整数时，并不会仅仅存储有效的二进制位。例如当 num} = 5 时，它的二进制表示为 (101)_2，而使用 32 位整数存储时的结果为：

(0000000000000000000000000000~0101)_2

因此我们需要首先找到 num 二进制表示最高位的那个 1，再将这个 1 以及更低的位进行取反。

如果 num 二进制表示最高位的 1 是第 i~(0 \leq i \leq 30) 位，那么一定有：

2^i \leq \textit{num} < 2^{i+1}

因此我们可以使用一次遍历，在 [0, 30] 中找出 i 的值。

在这之后，我们就可以遍历 num 的第 0 \sim i 个二进制位，将它们依次进行取反。我们也可以用更高效的方式，构造掩码 mask} = 2^{i+1} - 1，它是一个 i+1 位的二进制数，并且每一位都是 1。我们将 num 与 mask 进行异或运算，即可得到答案。

细节

当 i=30 时，构造 mask} = 2^{i+1} - 1 的过程中需要保证不会产生整数溢出。下面部分语言的代码中对该情况进行了特殊判断。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findComplement(int num) {
        int highbit = 0;
        for (int i = 1; i <= 30; ++i) {
            if (num >= (1 << i)) {
                highbit = i;
            }
            else {
                break;
            }            
        }
        int mask = (highbit == 30 ? 0x7fffffff : (1 << (highbit + 1)) - 1);
        return num ^ mask;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int findComplement(int num) {
        int highbit = 0;
        for (int i = 1; i <= 30; ++i) {
            if (num >= 1 << i) {
                highbit = i;
            } else {
                break;
            }            
        }
        int mask = highbit == 30 ? 0x7fffffff : (1 << (highbit + 1)) - 1;
        return num ^ mask;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int FindComplement(int num) {
        int highbit = 0;
        for (int i = 1; i <= 30; ++i) {
            if (num >= 1 << i) {
                highbit = i;
            } else {
                break;
            }            
        }
        int mask = highbit == 30 ? 0x7fffffff : (1 << (highbit + 1)) - 1;
        return num ^ mask;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findComplement(self, num: int) -> int:
        highbit = 0
        for i in range(1, 30 + 1):
            if num >= (1 << i):
                highbit = i
            else:
                break
        
        mask = (1 << (highbit + 1)) - 1
        return num ^ mask
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
var findComplement = function(num) {
    let highbit = 0;
    for (let i = 1; i <= 30; ++i) {
        if (num >= 1 << i) {
            highbit = i;
        } else {
            break;
        }            
    }
    const mask = highbit == 30 ? 0x7fffffff : (1 << (highbit + 1)) - 1;
    return num ^ mask;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
func findComplement(num int) int {
    highBit := 0
    for i := 1; i <= 30; i++ {
        if num < 1<<i {
            break
        }
        highBit = i
    }
    mask := 1<<(highBit+1) - 1
    return num ^ mask
}

复杂度分析

  • 时间复杂度：O(\log \textit{num})。找出 num 二进制表示最高位的 1 需要的时间为 O(\log \textit{num})。

  • 空间复杂度：O(1)。

 Comments
On this page
0476-数字的补数