assembly - 二进制补码快速方法

Question

求二进制补码的方法是:

1. Let x ̄ = the logical complement of x. The logical complement (also called the one’s complement) is formed by flipping all the bits in the number, changing all of the 1 bits to 0, and vice versa.
2. Let X = x ̄ + 1. If this addition overflows, then the overflow bit is discarded. By the definition of two’s complement, X ≡ −x.

我见过一个快速的方法，就是:

eg.

B = 00010110 D = 22

Flip everything after the first "1" counting from left side.

-B = 11101010 -D = -22

我无法理解这种方式的证明。

Answer 1

如果采用定义 -x = ~x + 1，那么如果我们将 x 表示为字符串 a10^k (a字符串 a 后跟 1 后跟 k 个零)，然后:

-(a10^k) =
// by definition
~(a10^k) + 1 =
// complement distributes over concatenation
~a01^k + 1 =
// carry through the 1s and set the 0
~a10^k

最后的结果，~a10^k，意思是“补左边，直到(不包括)最右边的1”。

这个证明对 x = 0 不成立，因为它不能写成 a10^k 的形式，等价性仍然成立:没有要补充的部分，因为没有最右边的 1，所以结果又是零，这是正确的。