计算机用补码代替负，然后用加法代替减法的想法让人惊艳。惊为天人的人才会这么干，我心想。但仔细一想，你会发现，事情并没这么简单。
1，有限位2进制数的加法计算本来就是在求同余
这一点很显然。一个k位2进制数能表示的数字的个数是2^k。如果从0开始算，最大的整数就是2^k-1。这些数以及他们的加法都显然生活在mod 2^k 里，永远也不能超过他。
2，补码的计算方法其实就是减法。
补码并未规避减法的存在。实际上，计算补码就是一个减法的过程。只不过：
a-b \ (mod n) =a+(n-b) \ (modn)
为什么n-b的计算要比a-b好呢？因为n一定是2^k，这个数就是2进制表示下的一组本征解（1<<k）。n比起a来说要好表示的多。
其次，n-b这个减法也好算的多。实际上，我们会有类似这样的算法笔试题：
用bit operation计算n-b。
n-b的技巧无非是，首先注意到n只有最高位是1。把n的traliling 0 变成1， 用这些全部的1去减一个（位数比自己小的）数，得到的结果很简单：
b中的1被1减，就得到0；0被1减，还是1。不存在任何借位的问题。这就是为什么n-b好算了。
那么，如何把n的traliling 0 全部变成1呢？
就是n-1了。这是2进制中翻转trailing 0的最好的做法。当然此做法同时把最低位的1变成了0。如果你不想这么做的话，你可以再和n 做一个or运算即可。
所以，世界上最简单的减法就这样完成了：
n-1-b
为了正确计算n-b
注意到n-1-b+1=n-b
因此，我们计算n-b的过程就是，把b每一位翻转，剩余的高位全部补1，最后再加1。当然，为了区别他和普通的正数，最高位置1。
一个例外是，如果你这样计算0 的负数，你最高位自然就是1了。不过在mod n 的运算中，0既可以是0，又可以是n。所以这个特别的数就计作n的负数，-n了。
网友评论