03.Number Complement

  1. 思路
  2. 计算mask方法一:
  3. 计算mask方法二:
  4. 计算mask方法三:
  5. 计算mask方法四:

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

注意:

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


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 jaytp@qq.com

文章标题:03.Number Complement

字数:500

本文作者:ihugo

发布时间:2017-03-12, 11:56:22

最后更新:2022-03-11, 02:46:44

原始链接:http://ihugo.cc/2017/03/12/03-Number-Complement/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。