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

Question

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.

Answer 1

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

Answer 2

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

Answer 3

All of these answers are correct, I suspect something is wrong with the code I'm using to test my function, because no matter what I do, I get 0 when I want 1 and 1 when I want 0

Answer 4

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.

Answer 5

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

Answer 6

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