题目描述

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

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

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

样例

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

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

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

说明

• 0 <= N < 10^9
• 本题与 476 相同。

算法

(位运算) $O(\log n)$

1. 此题的核心在于求出该数最高位 1 所代表的值，假设最高位的 1 在第 t 位上，则设 tot = 1 << t。最后答案为 num 取反，然后取后 t - 1 位，即按位与上 tot - 1。
2. 可以采用枚举数位的方式，但题解中采用了求 lowbit 的方式。
3. 注意特判输入为 0 的情况。

时间复杂度

• 最坏情况下需要遍历这个数的所有二进制位，故时间复杂度为 $O(\log n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int bitwiseComplement(int N) {
        if (!N) return 1;

        int tot = 0;
        for (int x = N; x; x -= x & -x)
            tot = x;

        return ~N & (tot - 1);
    }
};