2

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 );  
}

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).

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?

Cratylus
  • 52,998
  • 69
  • 209
  • 339
  • 1
    It's true for unsigned integers, for signed integers (e.g., `int`) the overflow invokes undefined behavior. – ouah Sep 21 '14 at 21:13
  • @ouah:When you say it is true, are you referring to my `...Two's complement addition is basically unsigned modulo arithmetic that is "converted" to two's complement, right?` – Cratylus Sep 21 '14 at 21:14
  • I'm referring to `(x + y) - x` evaluating to `x`. – ouah Sep 21 '14 at 21:17

2 Answers2

4

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).

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.

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.

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.

BadZen
  • 4,083
  • 2
  • 25
  • 48
  • *"this is to support the C standard easily on processors that do not use two's compliment math. Most do."* Modern C compilers actively perform optimizations based on the idea that signed overflow is undefined. – ouah Sep 21 '14 at 21:21
  • 1
    Unsigned math will always function as a group -- the standard requires it. Signed math is not required to by the C spec, but most processors use 2s complement which is a group. Unfortunatley, the C spec does not require the compiler to use the machine's 2s complement operations in all cases -- the optimizer can choose to do something else when overflows occur. – Chris Dodd Sep 21 '14 at 21:22
  • @ouah - Interesting. Can you provide a citation and/or show us a program compiled in gcc that produces such behavior? I have never seen it. – BadZen Sep 21 '14 at 21:22
  • @BadZen:1)If (a + b) can overflow then how can the order of addition not matter? 2) `1011` is -3 so far ok. I lost you in the `...Subtracting back yields 1010` What does that mean? We got -3. What is this subtracking back? – Cratylus Sep 21 '14 at 21:25
  • "Subtracting back" == evaluating the first expression on the left in your return line above. Think of it this way: moving to signed from unsigned in a 2's complement system of n bits is like evaluating the invertible map that sends [0..2^{n-1}-1] to [0..2^{n-1}-1], and [2^{n-1}..2^n-1] to [-2^{n-1}..-1], in order. That is to say f(x) = x for the first branch, and f(x) = -(2^n-x) in the second. Put this way, you can easily verify the commutative and associative properties I've claimed (ie. abelian). – BadZen Sep 21 '14 at 21:29
  • 1
    @BadZen Real life example: `int foo(int a) { return (x * 10) / 10; }`. Compile with `gcc` `-O0` and with `-O3`. Compute for example `foo(INT_MAX);`. With `-O3`, `(x * 10) / 10` is folded into `x` by exploiting the undefined behavior of signed overflows. – ouah Sep 21 '14 at 21:34
  • @BadZen:`Subtracting back yields 1010, or 0101+1 = 6`.But it is `-3-7=-10=10110` which becomes `0110` (truncates to 4 bits) which is 3 which is not equal to x. Why subtracting back gives 1010? Also 1010 is -6 and not 6 as you mention. – Cratylus Sep 21 '14 at 21:39
  • 0110 = 2^2*1 + 2^1*1 + 2^0*0 = 4+2 = 6. – BadZen Sep 21 '14 at 21:44
  • @BadZen:You are right. My bad. `0110` is 6.But what is the 1010 in your answer: `...yields 1010, or 0101+1 = 6.` – Cratylus Sep 21 '14 at 21:46
  • To negate a two's complement number, you invert the binary digits and then add 1. The 1010 is the raw value of the subtraction (you get to "borrow" a bit from the non-existent fifth-bit column, if you will) – BadZen Sep 22 '14 at 01:31
  • @BadZen:`To negate a two's complement number, you invert the binary digits and then add 1` But this is the process for one's complement – Cratylus Sep 22 '14 at 16:57
  • No, you don't add a 1 for one's complement - no offset because there is a -0. We're not working in ones' complement at all, as you indicated. If you're on a ones' complement machine, I'm not actually sure how overflow is "supposed to" work. Again, it's undefined. – BadZen Sep 24 '14 at 04:47
0

This is the old question, but hope my answer will be useful for someone.

This is because to fix a positive overflow (when x + y > TYPE_MAX) we need to subtract 2^n from the sum and to fix a negative one (when x + y < TYPE_MIN) we need to add 2^n (a bunch of math statements are needed to show this, so I decided not to include them in the answer).

Therefore if x + y is positively overflowed sum actually equals to x + y - 2^n. After this when we perform comparison we subtract x from sum which causes a negative overflow and hence we have sum - x actually equals to sum - x + 2^n. Thus, sum - x + 2^n = x + y - 2^n - x + 2^n = x. The same happens with another preposition.

E. Shcherbo
  • 1,128
  • 8
  • 15