博客

发现了一个问题自己还不是很懂，就是说如何求一个数的补数，举个例子，比如5，二进制是101，那么它的补数就应该是010就是2。

你可能会问了，这不是很简单吗？取反就行了啊，~5就行，事实上是这样子吗？当然不是了，因为5是101，但是它前边还有很多0。

如果按照无符号int来看的话，是32个bit。

为了简单，我们只写最后8个bit，是

0000 0101

那么它的补数2就是

0000 0010。

但是对5取反之后得到的是：

11111010

显然，取反是错误的。那么怎么做才是对的呢？

偷偷瞄了一眼答案。


第一步：寻找一个掩码（mask）


要找的这个掩码的特征应该是这个样子的。5的二进制是101，只占3个bit，那么这个掩码的最后3个bit要是0，其余全部是1。如下所示：

5：0000 0101

掩码：1111 1000


第二步：分别取反


~5 ：1111 1010

~掩码：0000 0111


第三步：相与


~5 & ~掩码 = 0000 0010

代码如下：

class Solution {
public:
    int findComplement(int num) {
        unsigned mask = ~0; //掩码初始为二进制全部是1
        while(num & mask)
            mask <<= 1;  //左移掩码
        return ~num & ~mask;
    }
};

特此记录，谨防忘记