03.Number Complement

作者 iHugo 日期 2017-03-12
03.Number Complement

给定一个正数,输出它的“补数”。求的方法是把二进制位置的数进行取反。

注意:

  1. 给定的正数在32位内
  2. 正数前面没有补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有两种方法。这里你可以用上面的例子数据代进去验证一下。

  1. output = input ^ mask
  2. output = mask - input

所以这个问题的关键是如何得到mask。

还有第三种思路是这样的。每次将input分别与其对应二进制位为1的数进行异或操作,就能得到output。

class Solution(object):
def findComplement(self, num):
i = 1
while num >= i:
num ^= i
i <<= 1
return num

计算mask方法一:

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方法二:

int mask = 0;
int j = 0;
while (mask < num)
{
mask += Math.pow(2, j);
j++;
}

从右往左不断的增加1的位数,直到mask >= num

计算mask方法三:

int mask = num;
mask |= mask >> 1;
mask |= mask >> 2;
mask |= mask >> 4;
mask |= mask >> 8;
mask |= mask >> 16;

每次与右移后的值进行与操作,移动的位数每次能扩大2倍。这样就能保证mask的所有二进制位都是1。

计算mask方法四:

mask = ((2<<int(math.log(num, 2)))-1)

利用数学函数能得到input的位数(int(math.log(num, 2))+1), 这样进1位减去1就得到了mask值。