是否有可能通过归纳证明，对于所有长度为 n 的序列，任何 0 字符串的二进制补码总是会导致 0？
我正在尝试使用价值公式来做到这一点，即
值 = -a_n-1 x 2^(n-1) + summation{i=0 to n} (a_i x 2^i)，其中 n = 字符串中的位数
问问题
3696 次
3 回答
1
111..111的 2 的补码不就是1（这意味着 111..111 代表 -1）吗？
于 2010-10-19T17:25:54.987 回答
1
您是否要求证明，例如，是的二进制补1111 1111码0000 0000？如果是这样，您无法证明它，因为它是错误的。的二进制补码1111 1111是0000 0001。
1111 1111
-> 0000 0000 <- one's complement
-> 0000 0001 <- add 1
回复您的编辑：当然。但是你不需要感应。反转所有位0_n以获得一个的补码给你1_n和添加1翻转所有位回到零（1 + 1 = 10并且进位位渗透到我们丢弃它的位置结束）。QED。
于 2010-10-19T17:28:08.377 回答
1
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）是一个数字零全零。翻转所有位将生成一个全为数： Ones
5) 位 0 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 中除 N_One:1 之外的所有位都为零。
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
由于第一个进位 (carry:1) 定义为 6.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。（始终忽略具有固定位域大小的机器的最后一个进位）
量子点
于 2010-10-20T20:51:59.717 回答