题目描述

给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。

样例

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

输入: 1
输出: 0
解释: 1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0。

说明

• 给定的整数保证在 32 位带符号整数的范围内。
• 你可以假定二进制数不包含前导零位。
• 本题与 1009 相同。

算法

(位运算) $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 findComplement(int num) {
        if (!num) return 1;

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

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