Function that checks for overflow in addition of unsigned ints

Question

I have to make functions that check for overflow in integer addition, subtraction, and unsigned int addition(using only ! ~ | & ^ + >> <<). I have functions figured out for signed integer addition and subtraction, but I can't figure out how to do one for unsigned int addition.

How would I go about doing this?

Here is the code I have for the 2 functions I have completed:

int twosAddOk(int x, int y){
    int z=x+y;
    int a=x>>31;
    int b=y>>31;
    int c=z>>31;
    return !!(a^b)|(!(a^c)&!(b^c));
}

int twosSubtractOK(int x, int y){
    int z=x+~y+1;
    return !(((x^y & x^z))>>31);
}

do you understand how numeric values are stored in `int`s in your c implementation? (almost certainly 2's complement)? — BurnsBA, Apr 05 '21 at 20:50
Do the calculation using a larger type, then check if the result is higher than the highest value of the original type. — Barmar, Apr 05 '21 at 20:50
See https://stackoverflow.com/questions/33948450/c-detect-unsigned-int-overflow-of-addition I'll let others decide if this a duplicate or not. — Andrew Henle, Apr 05 '21 at 20:53
@AndrewHenle I am not allowed to use if statements, only the operators i provided — ians, Apr 05 '21 at 20:55
@ians Why operator restriction? What application needs that? Looks like that would obfuscate code. — chux - Reinstate Monica, Apr 05 '21 at 21:47
unsigned addition cannot overflow by definion. It can only wraparound — 0___________, Apr 05 '21 at 23:03
Your code uses the assignment operator `=`, which is not on the approved list. (The point of this comment is that your restriction to use only those operators is silly.) — William Pursell, Apr 06 '21 at 18:18

mkayaalp · Answer 1 · 2021-04-06T19:27:58.243

0

You can calculate the carry-out from the MSB the hard way:

int unsignedAddOk(unsigned int x, unsigned int y){

    unsigned int x0=(~(1U<<31))&x; // MSB of x cleared
    unsigned int y0=(~(1U<<31))&y; // MSB of y cleared
    int c=(x0+y0)>>31; // Carry-in of MSB
    int a=x>>31; // MSB of x
    int b=y>>31; // MSB of y
    return !((a&b)|(a&c)|(b&c));
}

edited Apr 06 '21 at 19:27

answered Apr 06 '21 at 02:30

mkayaalp

2,631
10
17

@chux-ReinstateMonica Thanks. Is it fixed now? – mkayaalp Apr 06 '21 at 18:08
@chux-ReinstateMonica You're right. They are all actually boolean at that point. – mkayaalp Apr 06 '21 at 19:28

chux - Reinstate Monica · Answer 2 · 2021-04-06T20:16:26.800

Perhaps a solution without coding the magic number 31

// Return 1 on overflow
int unsigned_add_overflow_test(unsigned a, unsigned b) {
  // Add all but the LSBits and then add 1 if both LSBits are 1
  // When overflow would occur with a + b, sum's MSBit is set.
  unsigned sum = (a >> 1) + (b >> 1) + (a&b&1);
  // Test MSBit set
  //                vvv--------- All bits set
  return !!(sum & ~(-1u >> 1));
  //               ^^^^^^^^^^ -- All bits set, except MSBit
  //              ^^^^^^^^^^^ -- MSBit set, rest are 0 
}

Or as a one-liner

!!( ((a >> 1) + (b >> 1) + (a&b&1)) & ~(-1u >> 1)) )

Function that checks for overflow in addition of unsigned ints

2 Answers2