检查已签名的加法和abelian组中的溢出 [英] Check of overflow in signed addition and abelian groups

问题描述

我正在阅读为什么以下代码存在错误:

I was reading about why the following code is buggy:

int tadd_ok ( int x, int y ) {  
    int sum = x + y;  
    return ( sum - x == y ) && ( sum - y == x );  
}  

解释是二进制补码加成一个阿贝尔群，因此表达式
(x + y) - x的值等于y，无论加法是否溢出.
(与(x + y) - y)相同，其结果将为x).

The explanation was that two's complement addition forms an abelian group and so the expression
(x + y) - x with evaluate to y regardless if whether or not the addition overflows.
(Same for (x + y) - y) which will evaluate to x).

我不理解此解释或阿贝尔团体参考.二进制补码基本上是无符号模运算，可以转换"为二进制补码，对吧?
因此，例如，如果我们有4位，则我们的范围为[-8，7].
在示例中，如果我们有x = 7和y = 6，结果将溢出到6.这不等于y或x.
那么，为什么不考虑溢出总是相等的解释呢?

I don't understand this explanation or the abelian group reference. Two's complement addition is basically unsigned modulo arithmetic that is "converted" to two's complement, right?
So for example if we have 4 bits we have the range [-8, 7].
In the example if we had x = 7 and y = 6 the result overflows to 6. And that is not equal to either y or x.
So why is the explanation that the equality is always valid regardless of the overflow?

推荐答案

阿贝尔"组仅表示添加事物的顺序无关紧要-(a + b)+ c = a +(b + c)和(a + b)==(b + a).

An "abelian" group just means that the order that you add things doesn't matter - (a+b)+c = a+(b+c) and (a+b) == (b+a).

这对于C中的整数是正确的.@ouah指出溢出是未定义的，因此在技术上是正确的，但这是为了在不使用二进制补码数学的处理器上轻松支持C标准.大多数都这样做.

This is true of the integers in C. It is technically true as @ouah points out that overflow is undefined, but this is to support the C standard easily on processors that do not use two's compliment math. Most do.

在这些情况下，除非在编译器中发生了非常奇怪的事情(或不太奇怪，但是已经过优化-感谢@ouah)，否则无符号数学将作为一个阿贝尔群.

On those, unless something very strange (or not so strange, but optimized - thanks @ouah) is going on in the compiler, unsigned math will function as an abelian group.

在您的示例中，7 + 6 = 0111 + 0110 == 1101是-(0010 + 1)= -3.在二进制补码符号系统中，负数以二进制形式向下计数":1111为-1.减去收益1010或0101 + 1 = 6.

In your example, 7+6 = 0111 + 0110 == 1101 is -(0010+1) = -3. Negative numbers "count downward" in binary in a twos' complement signed system: 1111 is -1. Subtracting back yields 1010, or 0101+1 = 6.

这篇关于检查已签名的加法和abelian组中的溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！