Logical NOT (!) operator won't work with bitwise statement

2
votes

I am attempting to determine if I can compute the sum of two 32 bit integers without overflow, while making use of only certain bitwise and other operators. So, if the integers x and y can be added without overflow, the following code should return 1, and 0 otherwise. 

(((((x >> 31) + (y >> 31)) & 2) >> 1))

However, it returns 0 when it should be 1 and vice versa. When I employ the logical NOT (!) operator, or bitwise XOR (^) with 0x1, it does not fix the issue.

!(((((x >> 31) + (y >> 31)) & 2) >> 1))

(((((x >> 31) + (y >> 31)) & 2) >> 1) ^ 0x1)

^ these don't work.

Thanks in advance.

5
cbit-manipulationbitwise-operatorslogical-operators
My advice is to cheat: first cast to unsigned, so there's never an overflow. Then again, you pretty much need to anyway, since you don't know what you'll get from right shifting a negative number. – Jerry Coffin
@Jerry Coffin: even with unsigned there can still be overflow while adding two large negative numbers. – kriss
Hmm...a negative unsigned number. Just the concept already seems to cause an overflow... – Jerry Coffin
Just FYI, on most processors, it's far more efficient to just go ahead and add two integers, then check to see if overflow occurred than it is to determine if a computation is going to overflow before you perform it. – Stephen Canon
@Stephen, true, but IIRC that depends on Undefined Behavior caused by allowing signed integer arithmetic to overflow in the first place. Some DSPs saturate on overflow rather than wrapping, for instance. – RBerteig

5 Answers

8
votes

This is a bit cleaner:

~(x & y) >> 31

Update

kriss' comment is correct. all this code does is check that the two MSBs are both set.

I was just looking at kriss' answer, and it occurred to me that the same thing can be done using only a single addition, plus bitwise operators, assuming unsigned ints.

((x & 0x7FFFFFFF) + (y & 0x7FFFFFFF)) & 0x80000000 & (x | y)

The first parenthesised section sets both MSB to 0 then adds the result. Any carry will end up in the MSB of the result. The next bitmask isolates that carry. The final term checks for a set MSB on either x or y, which result in a carry overall. To meet the spec in the question, just do:

~(((x & 0x7FFFFFFF) + (y & 0x7FFFFFFF)) & 0x80000000 & (x | y)) >> 31
2
votes

Let's suppose both numbers are unsigned integers. If you work with signed integers, it would be a little be more tricky as there is two ways to get overflow, either adding two large positives of adding two large negative. Anyway checking the most significant bits won't be enough, as addition propagates carry bit, you must take it into account.

For unsigned integers, if you don't care to cheat an easy way is:

 (x+y < x) || (x+y < y)

This will work as most compilers won't do anything when overflow happen, just let it be.

You can also remarks that for overflow to happen at least one of the two numbers must have it's most significant bit set at 1. Hence something like that should work (beware, untested), but it's way more compilcated than the other version.

/* both Most Significant bits are 1 */
(x&y&0x80000000)        
/* x MSb is 1 and carry propagate */
 ||((x&0x80000000)&&(((x&0x7FFFFFFF)+y)&0x80000000))
/* y MSb is 1 and carry propagate */
 ||((y&0x80000000)&&(((y&0x7FFFFFFF)+x)&0x80000000))
1
votes

The logical ! is working fine for me.

me@desktop:~$ cat > so.c
#include <stdio.h>

void main() {
    int y = 5;
    int x = 3;
    int t;
    t = (((((x >> 31) + (y >> 31)) & 2) >> 1));
    printf("%d\n", t);
    t = !(((((x >> 31) + (y >> 31)) & 2) >> 1));
    printf("%d\n", t);
}
^D
me@desktop:~$ gcc -o so so.c
me@desktop:~$ ./so
0
1
me@desktop:~$ uname -a
Linux desktop 2.6.32-23-generic #37-Ubuntu SMP Fri Jun 11 07:54:58 UTC 2010 i686 GNU/Linux
1
votes

There is no simple bit-arithmetic-based test for overflow because addition involves carry. But there are simple tests for overflow that do not involve invoking overflow or unsigned integer wrapping, and they're even simpler than doing the addition then checking for overflow (which is of course undefined behavior for signed integers):

For unsigned integers x and y: (x<=UINT_MAX-y)

For signed integers, first check if they have opposite signs. If so, addition is automatically safe. If they're both positive, use (x<=INT_MAX-y). If they're both negative, use (x>=INT_MIN-y).

0
votes

Are those signed integers by any chance? Your logic looks like it should be fine for unsigned integers (unsigned int) but not for regular ints, since in that case the shift will preserve the sign bit.