476.数字的补数

对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。

• 例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。

给你一个整数 num ，输出它的补数。

示例 1：

1
2
3

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

Solution

思路是找到num的二进制表示的第一个1，之后对每一位进行取反操作

如果num二进制表示的最高位的1是第i位，那么一定有$2^i≤num≤2^{i+1}$,因此可以用一次遍历找出i的值,之后，可以用过构造掩码的方式，进行异或运算，来得到答案

1
2
3
4
5
6
7
8

class Solution {
    public int findComplement(int num) {
       int n = 2;
        while(n - 1 < num)
            n <<= 1;
        return (n - 1) ^ num;
    }
}