首页 > 代码库 > 计算机中整数加法满足结合律吗
计算机中整数加法满足结合律吗
今天看《程序设计语言概念》（Concepts of Programming Language），第七章“结合性”一节中有这么一段：
某些计算机中的整数加法不具有结合性。例如，假设一个程序要计算“A + B + C + D”，其中A、C是很大的正数，B、D是绝对值很大的负数。在这种情况下，将B加到A并不会导致溢出，但将C加到A就会溢出。B和D与此类似。
这段话很好理解，因为只要是程序员，整数计算可能会溢出是基本的常识。但这段话只谈到计算的中间结果发生溢出的情况。如果不考虑中间结果而将重点放在最终结果上，计算顺序是否依然会对结果产生影响呢？也就是说，计算机中的加法满足结合律吗？即：
(a + b) + c
是否一定等于
(a + c) + b
呢？
首先，如果每个中间结果以及最终结果都没有溢出，可以肯定必然是满足结合律的，否则就是计算机自身有错误。
如果中间结果发生了溢出会怎样？我们不妨编写一个简单的程序验证一下。这里我们选择四个整数，a和c是两个是很大的正数，b和d是两个很小的负数（即绝对值很大的负数）。
int a = 2147483392; //0x7fffff00;int b = -2147479553; //0x80000fff;int c = 2146500592; //0x7ff0fff0;int d = -2147421968; //0x8000f0f0;int sum1 = ((a + b) + c) + d;int sum2 = (a + b) + (c + d);int sum3 = (a + c) + (b + d);System.out.println("((a + b) + c) + d=" + sum1);System.out.println("(a + b) + (c + d)=" + sum2);System.out.println("(a + c) + (b + d)=" + sum3);
sum1为从左到右依次计算a+b+c+d的和；sum2先计算a+b和c+d，然后再计算二者的和；sum3则先计算a+c和b+d，然后再求和。通过代码可以看出，sum1和sum2的中间结果没有发生溢出，但sum3在计算a+c和b+d时都发生了溢出。下面来看看实际运行结果：
((a + b) + c) + d=-917537(a + b) + (c + d)=-917537(a + c) + (b + d)=-917537
可以看到无论顺序如何结果都是正确的。所以我们可以得出结论：
计算机中的整数加法运算满足结合律
这里还有一个问题，在上面的例子中，虽然中间结果发生了溢出，但最终结果是没溢出的。那如果最终结果也溢出了会怎么样？答案是不同计算顺序得到的结果仍然一样，只不过结果都是错的（都溢出了）。这是由计算机本身有限的精度导致的，和结合律无关，所以这种情况仍然认为是符合结合律的。你可以自己写个程序来验证这一点。
不过要注意，这个结论是有限定条件的，对现代大多数计算机系统来说该结论都成立，因为这些系统通常都采用“二进制补码”的方式来存储整数，而二进制补码的加法运算是符合结合律的。不满足结合律的例子也是有的，比如BCD码的加法运算。
------------------------------------------------------------------
写到这里，我想到了一个老题目：如何在不引入临时变量的情况下交换2个整数的值？一般来说，有2种方法可以做到，一种是使用加法，另一种是使用异或：
a = a + b;b = a - b;a = a - b;
a = a ^ b;b = a ^ b;a = a ^ b;
有人说第一种方法有问题，原因是将a和b相加时可能会溢出。如果你看了这篇文章，就会知道这种说法是错误的了——虽然a+b可能会溢出，但最后仍能得到正确的结果。要说缺点，只是它的效率比第二种要低一些。但话说回来，它的可读性却要优于第二种。
------------------------------------------------------------------
补码简介
下面简单介绍一下补码，如果对此不感兴趣或已比较熟悉请略过。二进制补码（Two‘s complement）采用“2^N的补”的方式存储的整数编码（其中N为整数的位长）。相比而言，另一种存储方式“反码”采用的是“1的补”，即逐位计算各个位的补（1的补为0，0的补为1，在二进制中这和取反是一样的），因此反码的英文名称为“One‘s complement”。
补码可以认为是对反码的改进，这不但因为补码中统一了“正零和负零”，还因为其计算也要比反码容易。最主要的一点是补码不用考虑进位（即溢出位），而反码则必须考虑。补码的另一个优点是其符号位同时也是计算位，因此计算时无需对正数和负数区别对待，这一点和反码一样。与补码和反码不同，原码则必须同时考虑数的正负和进位，因此很少有系统采用原码的方式来存储整数。
下面分别用补码和反码的方式来计算“10 - 1”，以此加深理解。
由于大多数计算机只实现了加法而没有减法，因此“10 - 1”实际上是转换为“10 + (-1)”来计算的。为了简单，这里假设整数只有8位。
补码的计算过程如下（-1的补码为“1111 1111”）：
0000 1010
+ 1111 1111
——————
1 0000 1001
结果发生了溢出，产生了一个进位，对补码来说简单忽略即可，因此最后的结果为“9”。
注意这里的溢出属于正常溢出。相比之下，如果正数+正数结果为负数，或负数+负数结果为正数时，则说明发生了不正常的溢出。正常的溢出结果仍然是正确的（这正是补码的特性），而不正常的溢出得到的是错误的结果。
反码的计算过程为（-1的反码为“1111 1110”）：
0000 1010
+ 1111 1110
——————
1 0000 1000
同样发生了溢出，但此时不能忽略进位，否则将得到错误结果“8”，因此还需要把进位加到结果上：
0000 1000
+ 1
——————
0000 1001
得到最终结果“9”。
总结
最后再来简单总结一下。在大多数计算机系统中，整数的加法运算满足结合律。具体来说，如果最终结果没有溢出，即使计算过程的中间结果出现了溢出也不会影响最终结果。而如果最终结果本身就是溢出的，改变计算顺序仍然会得到一致的结果，这时候仍然认为是满足结合律的。
虽然这篇文章对实际编程可能用处不大，因为我们通常只需注意最终结果不要溢出即可，对中间过程无需在意。但这篇文章为这个结论提供了一定的理论支持，以帮助我们加深对计算机整数加法运算的理解。
参考资料：
有符号数的表示：http://en.wikipedia.org/wiki/Signed_number_representations
反码：http://en.wikipedia.org/wiki/Ones%27_complement
补码：http://en.wikipedia.org/wiki/Two%27s_complement
BCD码：http://en.wikipedia.org/wiki/BCD_code
计算机中整数加法满足结合律吗
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。