476. 数字的补数

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

注意:

  • 给定的整数保证在32位带符号整数的范围内。
  • 你可以假定二进制数不包含前导零位。
    示例 1:

输入: 5

输出: 2

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

Solution：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findComplement(int num) {
        int cot = 0;
        int temp = num;
        while(1){
            if(num == 0) break;
            num = num >> 1;
            cot++;
        } 
        int mark = 0xffffffff;
        return ~temp ^ (mark << cot);
    }
};

首先找到该数是从哪一位开始才算有效（即不包含前面零的位置。）
再将该数所有位取反，
然后用全位置的1左移cot次，与值异或即可。

异或：不同为一，相同为零，所以当前面的零取反后成为一后，相应位置与1异或，会恢复成为0，之后的有效位还保持不变。