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

2018-06-02 18:28:47

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.

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

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

链接地址: http://www.djcxy.com/p/9884.html

上一篇: 了解整数上单个＆符号运算符（＆）的行为

下一篇: 逻辑NOT（！）运算符不适用于按位语句