Mixing
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 );
}
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?
c types integer integer-overflow integer-arithmetic
asked Sep 21 '14 at 21:01
CratylusCratylus
33.7k53176299
add a comment |
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?
c types integer integer-overflow integer-arithmetic
asked Sep 21 '14 at 21:01
CratylusCratylus
33.7k53176299
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) - xevaluating tox.
– ouah
Sep 21 '14 at 21:17
add a comment |
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?
c types integer integer-overflow integer-arithmetic
asked Sep 21 '14 at 21:01
CratylusCratylus
33.7k53176299
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?
c types integer integer-overflow integer-arithmetic
c types integer integer-overflow integer-arithmetic
asked Sep 21 '14 at 21:01
CratylusCratylus
33.7k53176299
asked Sep 21 '14 at 21:01
CratylusCratylus
33.7k53176299
edited Sep 21 '14 at 21:30
Cratylus
asked Sep 21 '14 at 21:01
CratylusCratylus
33.7k53176299
asked Sep 21 '14 at 21:01
CratylusCratylus
33.7k53176299
asked Sep 21 '14 at 21:01
CratylusCratylus
33.7k53176299
33.7k53176299
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) - xevaluating tox.
– ouah
Sep 21 '14 at 21:17
add a comment |
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) - xevaluating tox.
– ouah
Sep 21 '14 at 21:17
1
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
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
@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
I'm referring to
(x + y) - x evaluating to x.– ouah
Sep 21 '14 at 21:17
add a comment |
1 Answer
1
active
oldest
votes
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.
answered Sep 21 '14 at 21:17
BadZenBadZen
2,54711335
"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)1011is -3 so far ok. I lost you in the...Subtracting back yields 1010What does that mean? We got -3. What is this subtracking back?
– Cratylus
Sep 21 '14 at 21:25
1
@BadZen Real life example:int foo(int a) { return (x * 10) / 10; }. Compile withgcc-O0and with-O3. Compute for examplefoo(INT_MAX);. With-O3,(x * 10) / 10is folded intoxby exploiting the undefined behavior of signed overflows.
– ouah
Sep 21 '14 at 21:34
|
show 7 more comments
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f25963827%2fcheck-of-overflow-in-signed-addition-and-abelian-groups%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
answered Sep 21 '14 at 21:17
BadZenBadZen
2,54711335
"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)1011is -3 so far ok. I lost you in the...Subtracting back yields 1010What does that mean? We got -3. What is this subtracking back?
– Cratylus
Sep 21 '14 at 21:25
1
@BadZen Real life example:int foo(int a) { return (x * 10) / 10; }. Compile withgcc-O0and with-O3. Compute for examplefoo(INT_MAX);. With-O3,(x * 10) / 10is folded intoxby exploiting the undefined behavior of signed overflows.
– ouah
Sep 21 '14 at 21:34
|
show 7 more comments
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.
answered Sep 21 '14 at 21:17
BadZenBadZen
2,54711335
"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)1011is -3 so far ok. I lost you in the...Subtracting back yields 1010What does that mean? We got -3. What is this subtracking back?
– Cratylus
Sep 21 '14 at 21:25
1
@BadZen Real life example:int foo(int a) { return (x * 10) / 10; }. Compile withgcc-O0and with-O3. Compute for examplefoo(INT_MAX);. With-O3,(x * 10) / 10is folded intoxby exploiting the undefined behavior of signed overflows.
– ouah
Sep 21 '14 at 21:34
|
show 7 more comments
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.
answered Sep 21 '14 at 21:17
BadZenBadZen
2,54711335
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.
answered Sep 21 '14 at 21:17
BadZenBadZen
2,54711335
edited Sep 21 '14 at 21:25
answered Sep 21 '14 at 21:17
BadZenBadZen
2,54711335
answered Sep 21 '14 at 21:17
BadZenBadZen
2,54711335
answered Sep 21 '14 at 21:17
BadZenBadZen
2,54711335
2,54711335
"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)1011is -3 so far ok. I lost you in the...Subtracting back yields 1010What does that mean? We got -3. What is this subtracking back?
– Cratylus
Sep 21 '14 at 21:25
1
@BadZen Real life example:int foo(int a) { return (x * 10) / 10; }. Compile withgcc-O0and with-O3. Compute for examplefoo(INT_MAX);. With-O3,(x * 10) / 10is folded intoxby exploiting the undefined behavior of signed overflows.
– ouah
Sep 21 '14 at 21:34
|
show 7 more comments
"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)1011is -3 so far ok. I lost you in the...Subtracting back yields 1010What does that mean? We got -3. What is this subtracking back?
– Cratylus
Sep 21 '14 at 21:25
1
@BadZen Real life example:int foo(int a) { return (x * 10) / 10; }. Compile withgcc-O0and with-O3. Compute for examplefoo(INT_MAX);. With-O3,(x * 10) / 10is folded intoxby exploiting the undefined behavior of signed overflows.
– ouah
Sep 21 '14 at 21:34
"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
"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
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
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
@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
@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
1
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 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
|
show 7 more comments
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f25963827%2fcheck-of-overflow-in-signed-addition-and-abelian-groups%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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) - xevaluating tox.– ouah
Sep 21 '14 at 21:17