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。

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