二的补码证明

Question

有没有可能通过归纳法证明，对于所有长度为n的序列，任何0的字符串的2的补码都会得到0？

我试图使用值公式来实现这一点，即

值= -a_n-1 x 2^(n-1) +求和{i=0 to n} (a_i x 2^i)，其中n=字符串中的位数

Answer 1

111..111 的2的补码不就是1 (这意味着111..111代表-1)吗？

Answer 2

您是否要求证明，例如，1111 1111的两个补码是0000 0000？如果是这样，你不能证明它，因为它是假的。这两者对1111 1111的补充是0000 0001。

    1111 1111
->  0000 0000 <- one's complement
->  0000 0001 <- add 1

对您的编辑的回应:当然可以。但你不需要归纳。反转0_n的所有位以获得1的补码，得到1_n，并添加1将所有位反转回0 (1 + 1 = 10和进位位一直渗透到我们丢弃它的末尾)。QED。

Answer 3

1)定义X的两个补码:翻转X和1的位

2)两个变量的1位二进制和(http://www.play-hookey.com/digital/adder.html) (第一个变量为b1，第二个变量为b2 )。b1:X表示变量中的X位)

r1 = b1:1 XOR b2:1
carry = b1:1 AND b2:1

2.1)如果两个比特都是b1:1和b2:1

r1 = 0  (always)
carry = 1 (always)

3)两个变量2位的二进制和

r1 = b1:1 XOR b2:1 
carry1 = b1:1 AND b2:1

r2 = (b1:2 XOR b2:2) XOR carry:1
carry2 = (b1:2 AND b2:2) OR (b1:2 AND carry:1) OR (b2:2 AND carry:1)

3.1)从2.1开始，我们可以减少

carry2 = (b1:2 AND b2:2) OR (b1:2 AND 1) OR (b2:2 AND 1)
carry2 = b1:2 OR b2:2

4)是一个数字零全零。翻转所有位将生成一个全一数字:1

5)位0 XOR XOR=XOR(XOR真值表)

6)对数字零应用(1)

6.1)翻转

 Flipping Zero = Ones

6.2)总和1

 result = Ones + N_One (N_One = 00...001)
 result:1 = 0 (from 2.1)
 carry:1 = 1 (from 2.1)

6.3)因为除了N_One:1之外来自N_One的所有位都是零。

 result:n = (Ones:n XOR N_One:n) XOR carry:(n-1) (from 3)
 result:n = (Ones:n XOR 0) XOR carry:(n-1) (definition of N_One 6.2)
 result:n = Ones:n XOR carry:(n-1)

6.4)从3.1开始

carry:n = Ones:n OR N_One:n -> if carry:n-1 is 1
carry:n = 1 OR 0            -> if carry:n-1 is 1
carry:n = 1                 -> if carry:n-1 is 1

由于6.1中的第一个进位(进位:1)被定义为1，因此所有进位都被定义为1

7)从6.3到6.4

 result:n = Ones:n XOR carry:(n-1)
 result:n = 1 XOR 1
 result:n = 0

对于任何n值，证明(~n+1)始终为0。(固定位域大小的机器的最后一个进位总是被忽略)

QED