binary - 补码是可分配的吗？

Question

我知道它是关联和交换的：

那是，

(~x1 + ~x2) + ~x3 = ~x1 + (~x2 + ~x3) 

和

~x1 + ~x2 = ~x2 + ~x1

但是，对于我尝试过的案例，它似乎没有分配性，即，

~x1 + ~x2 != ~(x1 + x2)

这是真的？有证据吗？

我有如下C代码：

int n1 = 5;
int n2 = 3;
result = ~n1 + ~n2 == ~(n1 + n2);

int calc = ~n1;  
int calc0 = ~n2;  
int calc1 = ~n1 + ~n2;  
int calc2 = ~(n1 + n2);

printf("(Part B: n1 is %d, n2 is %d\n", n1, n2);
printf("Part B: (calc is: %d and calc0 is: %d\n", calc, calc0); 
printf("Part B: (calc1 is: %d and calc2 is: %d\n", calc1, calc2);
printf("Part B: (~%d + ~%d) == ~(%d + %d) evaluates to %d\n", n1, n2, n1, n2, result); 

这给出了以下输出：

Part B: (n1 is 5, n2 is 3
Part B: (calc is: -6 and calc0 is: -4
Part B: (calc1 is: -10 and calc2 is: -9
Part B: (~5 + ~3) == ~(5 + 3) evaluates to 0

Answer 1

[我知道这真的很老了，但我有同样的问题，而且由于最重要的答案是矛盾的......]

一个人的恭维确实是分配性的。您的代码中的问题（以及 Kaganar 的那种但不正确的答案）是您正在丢弃进位位 - 您可以在两个 s 的恭维中做到这一点，但不能在一个人的恭维中做到这一点。

无论您使用什么来存储总和，都需要比求和更多的内存空间，这样您就不会丢失进位位。然后将进位位折叠回用于存储操作数的位数以获得正确的总和。这在一个人的补码算术中称为“结束进位”。

来自维基百科文章（https://en.wikipedia.org/wiki/Signed_number_representations#Ones '_complement）：

要将这个系统中表示的两个数字相加，需要进行传统的二进制加法，但随后需要进行结束进位：即，将任何结果进位加回到结果和中。要了解为什么这是必要的，请考虑以下示例，该示例显示了将 -1 (11111110) 与 +2 (00000010) 相加的情况：

      binary    decimal
    11111110     –1
 +  00000010     +2
 ───────────     ──
  1 00000000      0   ← Not the correct answer
           1     +1   ← Add carry
 ───────────     ──
    00000001      1   ← Correct answer

在前面的例子中，第一个二进制加法得到 00000000，这是不正确的。正确的结果 (00000001) 仅在重新添加进位时出现。

我稍微更改了您的代码，以便更轻松地自己进行数学检查和测试。使用有符号整数数据类型可能需要更多考虑，或者考虑端接借用而不是携带。我没有走那么远，因为我的应用程序都是关于校验和的（即无符号的，只有加法）。

unsigned short n1 = 5;  //using 16-bit unsigned integers
unsigned short n2 = 3;

unsigned long oc_added = (unsigned short)~n1 + (unsigned short)~n2; //32bit
/*  Fold the carry bits into 16 bits */
while (oc_added >> 16)
    oc_added = (oc_added & 0xffff) + (oc_added >> 16);

unsigned long oc_sum = ~(n1 + n2);  //oc_sum has 32 bits (room for carry) 
/*  Fold the carry bits into 16 bits */
while (oc_sum >> 16)
    oc_sum = (oc_sum & 0xffff) + (oc_sum >> 16);

int result = oc_added == oc_sum;

unsigned short calc = ~n1;
unsigned short calc0 = ~n2;
unsigned short calc1 = ~n1 + ~n2;  //loses a carry bit
unsigned short calc2 = ~(n1 + n2);

printf("(Part B: n1 is %d, n2 is %d\n", n1, n2);
printf("Part B: (calc is: %d and calc0 is: %d\n", calc, calc0);
printf("Part B: (calc1 is: %d and calc2 is: %d\n", calc1, calc2);
printf("Part B: (~%d + ~%d) == ~(%d + %d) evaluates to %d\n", n1, n2, n1, n2, result);

Answer 2

查看有关Ones' 补码的 Wikiepdia 文章。补码中的加法在必须将溢出位添加到最低位的位置进行结束。

由于~(NOT) 等价-于一个补码中的 (NEGATE)，我们可以将其重写为：

-x1 + -x2 = -(x1 + x2)

哪个是对的。

Answer 3

一个补码用于表示固定宽度寄存器中的负数和正数。要分配超过加法，必须应用以下内容：~a + ~b= ~(a + b)。OP 状态+表示添加“两个二进制数”。这本身是模糊的，但是如果我们把它理解为添加无符号二进制数，那么不，一个人的恭维不是分配性的。

请注意，一个的补码中有两个零：所有位都是 1 或所有位都是零。

检查以查看~0 + ~0 != ~(0 + 0): ~0是否为零。然而，~0由所有的代表。将它添加到自身中会使它加倍——与左移相同——因此在右手数字中引入了一个零。但这不再是两个零之一。

然而，0是零，0 + 0也是零，因此也是~(0 + 0)。但左边不为零，所以分布不成立。

另一方面......考虑两个的恭维：翻转所有位并添加一个。如果注意特别对待一个人的恭维中的否定，那么那个版本的“二进制加法”类似于两个人的恭维并且是分配的，因为你最终得到一个熟悉的商环，就像在两个人的恭维中一样。

前面提到的Wikipedia 文章有更多关于处理加法以允许预期的算术行为的详细信息。

Answer 4

根据德摩根定律：

 ~(x1 + x2) = ~x1 * ~x2