1009-十进制整数的反码

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

每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 "101"，11 可以用二进制 "1011"
表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。

二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。

给你一个十进制数 N，请你返回其二进制表示的反码所对应的十进制整数。

示例 1：

**输入：** 5
**输出：** 2
**解释：** 5 的二进制表示为 "101"，其二进制反码为 "010"，也就是十进制中的 2 。

示例 2：

**输入：** 7
**输出：** 0
**解释：** 7 的二进制表示为 "111"，其二进制反码为 "000"，也就是十进制中的 0 。

示例 3：

**输入：** 10
**输出：** 5
**解释：** 10 的二进制表示为 "1010"，其二进制反码为 "0101"，也就是十进制中的 5 。

提示：

  1. 0 <= N < 10^9
  2. 本题与 476：https://leetcode-cn.com/problems/number-complement/ 相同

方法一：位运算

思路与算法

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

(0000000000000000000000000000~0101)_2

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

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

2^i \leq n < 2^{i+1}

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

在这之后，我们就可以遍历 n 的第 0 \sim i 个二进制位，将它们依次进行取反。我们也可以用更高效的方式，构造掩码 mask} = 2^{i+1} - 1，它是一个 i+1 位的二进制数，并且每一位都是 1。我们将 n 与 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 bitwiseComplement(int n) {
        int highbit = 0;
        for (int i = 1; i <= 30; ++i) {
            if (n >= (1 << i)) {
                highbit = i;
            }
            else {
                break;
            }            
        }
        int mask = (highbit == 30 ? 0x7fffffff : (1 << (highbit + 1)) - 1);
        return n ^ mask;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int bitwiseComplement(int n) {
        int highbit = 0;
        for (int i = 1; i <= 30; ++i) {
            if (n >= 1 << i) {
                highbit = i;
            } else {
                break;
            }            
        }
        int mask = highbit == 30 ? 0x7fffffff : (1 << (highbit + 1)) - 1;
        return n ^ mask;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int BitwiseComplement(int n) {
        int highbit = 0;
        for (int i = 1; i <= 30; ++i) {
            if (n >= 1 << i) {
                highbit = i;
            } else {
                break;
            }            
        }
        int mask = highbit == 30 ? 0x7fffffff : (1 << (highbit + 1)) - 1;
        return n ^ mask;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def bitwiseComplement(self, n: int) -> int:
        highbit = 0
        for i in range(1, 30 + 1):
            if n >= (1 << i):
                highbit = i
            else:
                break
        
        mask = (1 << (highbit + 1)) - 1
        return n ^ mask
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
var bitwiseComplement = function(n) {
    let highbit = 0;
    for (let i = 1; i <= 30; ++i) {
        if (n >= 1 << i) {
            highbit = i;
        } else {
            break;
        }            
    }
    const mask = highbit == 30 ? 0x7fffffff : (1 << (highbit + 1)) - 1;
    return n ^ mask;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
func bitwiseComplement(n int) int {
    highBit := 0
    for i := 1; i <= 30; i++ {
        if n < 1<<i {
            break
        }
        highBit = i
    }
    mask := 1<<(highBit+1) - 1
    return n ^ mask
}

复杂度分析

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

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

 Comments
On this page
1009-十进制整数的反码