03.Number Complement
给定一个正数，输出它的“补数”。求的方法是把二进制位置的数进行取反。
注意：
- 给定的正数在32位内
- 正数前面没有补0。比如2（B10）,在它的前面没有0。
例子1：
输入: 5
输出: 2
解释: 5的二进制数是101 (前面不补充0), 它的补数是010。所以输出是2。
例子2:
输入: 1
输出: 0
解释: 1的二进制是1 (前面不补充0), 它的补数是0。因此输出是0。
思路
假设输入数为input, 输出为output, 设mask的二进制位数与input相等，且每一位都为1。
这里求input有两种方法。这里你可以用上面的例子数据代进去验证一下。
- output = input ^ mask
- output = mask - input
所以这个问题的关键是如何得到mask。
还有第三种思路是这样的。每次将input分别与其对应二进制位为1的数进行异或操作，就能得到output。
1
2
3
4
5
6
7
class Solution(object):
def findComplement(self, num):
i = 1
while num >= i:
num ^= i
i <<= 1
return num计算mask方法一：
1
2
3
4
5
6
var flipMask: UInt32 = ~0
let numUInt32 = UInt32(num)
while ((numUInt32 & flipMask) != 0) {
flipMask <<= 1
}
let mask = ~flipMask;将全是’1’的UInt32数不断的左移，直到(numUInt32 & flipMask) == 0停止，然后再对flipMask取反就能得到要求的mask。
计算mask方法二：
1
2
3
4
5
6
7
int mask = 0;
int j = 0;
while (mask < num)
{
mask += Math.pow(2, j);
j++;
}从右往左不断的增加1的位数，直到mask >= num。
计算mask方法三：
1
2
3
4
5
6
int mask = num;
mask |= mask >> 1;
mask |= mask >> 2;
mask |= mask >> 4;
mask |= mask >> 8;
mask |= mask >> 16;每次与右移后的值进行与操作，移动的位数每次能扩大2倍。这样就能保证mask的所有二进制位都是1。
计算mask方法四：
1
mask = ((2<<int(math.log(num, 2)))-1)利用数学函数能得到input的位数(int(math.log(num, 2))+1), 这样进1位减去1就得到了mask值。
