3 ms·
EDIT 2: Editing... EDIT 1: as spotted by @pbsd this was not working good with some values... I have added a way of checking the overflow and I have tested it:
by professorTuring 12y ago
EDIT 2: Editing...
EDIT 1: as spotted by @pbsd this was not working good with some values...
I have added a way of checking the overflow and I have tested it:
#define BITS (8*sizeof(int))-1
int checked_add(int a, int b, int *rp)
{
*rp = a+b;
return (a^b) < 0 ? 0 : (a^(*rp)) < 0 ? 1 : 0) ;
}
It is around 30% faster than the fastest in the blog and I believe the code is way cleaner. What we are doing is checking if all of the values has the same sign (the "^" is just a "xor"), if so, no overflow in other case, overflow.
This is the testing program (g++ compliant):
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define BITS (8*sizeof(int))-1
int checked_add2(int a, int b, int *rp) {
uint ur = (uint)a + (uint)b;
uint sr = ur >> (BITS-1);
uint sa = (uint)a >> (BITS-1);
uint sb = (uint)b >> (BITS-1);
*rp = ur;
return
(sa && sb && !sr) ||
(!sa && !sb && sr);
}
int checked_add(int a, int b, int *rp)
{
*rp = a+b;
return ((a^b) | (a^(*rp)) < 0) ? 1 : 0 ;
}
int main(int argc, char* argv[])
{
int a, b, c;
long clong;
srand(time(NULL));
for(unsigned int i = 0; i < 50000000; ++i)
{
bool overflow = false;
a = rand();
b = rand();
clong = (long)a + (long)b;
overflow = checked_add(a,b,&c);
if(clong != (long)c && !overflow)
printf("Overflow not detected %i + %i = %i \n", a, b, c);
}
return 0;
}
Time for "checked_add": 2.694s
Time for "checked_add2": 3.200s
This is the dump (6 instructions so far): http://goo.gl/cnBKdS http://goo.gl/cnBKdS
- pbsd 12y agoYour function is incorrect. Consider the case a = b = 0x80000000.
- professorTuring 12y agoI might be missing something, but I have tested it and it gives me "0" and no overflow. edit: Ok, I do missed one spot (my mind tricked me), the answer shouldn't be 0.
- professorTuring 12y agoOk, I think this should do the trick: return((a ^ b) | (a ^ (*rp)) < 0) ? 1 : 0; doesn't it?
- pbsd 12y agoNot yet. Consider a = -1, b = 1. Due to the OR, any a and b with different signs will return overflow.
- professorTuring 12y agoOk this is my dumbest time in life xD (I just directly didn't take into consideration that part because it never has overflow...)...
- barrkel 12y agoMost people don't appreciate how complicated C's mix of signed and unsigned is, especially when undefined behaviour of signed overflow is included.
- professorTuring 12y agoDefinitely. Child, this is why I always add unit tests.
- aardvark179 12y agoUnfortunately signed overflow behavior is undefined in C so you can't guarantee your XOR with rp will give the expected result. This is partly why the article is so careful in its casting and the order of its checks. This actually easier to do in Java and many other languages because signed arithmetic is precisely defined.
- IsTom 12y agoOne of points of the article is that if you write a+b then compiler is free to assume that no overflow happens. If the compiler was sufficiently smart then if you wrote if(checked_addr(a,b,rp)) { //something 1 } else { //something 2 } then compiler is free to assume no overflow happens and replace code with: checked_add(a,b,rp); //something 2