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
值。