Weird behavior of & operator in C

Question

As part of a puzzle I am asked to implement a function which checks if two ints can be added together without overflow. Legal ops: ! ~ & ^ | + << >>.

For example for x = 0x80000000 and y = 0x80000000 the function should return 0 since it is overflowing but for x = 0x80000000 and y = 0x70000000 the result would be 1.

My solution so far is:

int addOK(int x, int y) {
    int mask = ~(1 << 31);        // 0x7fffffff
    int newX = (mask & (x >> 1)); // Shift 1 to the right to make space for overflow bit
    int newY = (mask & (y >> 1));
    int add = newX + newY;        // Add shifted x and y - overflow bit will be the MSB
    int res = (add & ~mask);      // Set all bits to 0 except MSB - MSB 1 iff overflow 0 otherwise
    int endRes = !res;            // 0x80000000 -> 0x00000000, 0x00000000 -> 0x00000001
    printf("mask %x newX %x newY %x add %x ~mask %x res %x endRes %x\n",mask, newX, newY, add, ~mask, res, endRes);
    return endRes;
}

The function prints the following for x = 0x80000000 and y = 0x80000000:

mask 7fffffff newX 40000000 newY 40000000 add 80000000 ~mask 80000000 res 0 endRes 1

Now my question is why is res 0? it should be 0x80000000 because both add and ~mask are 0x80000000. Can anyone explain this behavior to me?

You know shifting into the sign bit [is bad](http://stackoverflow.com/questions/4009885/arithmetic-bit-shift-on-a-signed-integer), right? Any particular reason you're not just using `INT_MAX` rather than trying to contrive it on your own? — WhozCraig, Sep 22 '14 at 20:05
Ok thanks; this is strange. I'm not supposed to use any constants larger than one byte for this task. — user3273046, Sep 22 '14 at 20:19
Can you try the same code on a different machine e.g. linux? — Linard Arquint, Sep 22 '14 at 20:21
I just used the make command in my terminal. `make -v GNU Make 3.81 Copyright (C) 2006 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. This program built for i386-apple-darwin11.3.0`. My Mac is on a 64 bit architecture. — user3273046, Sep 22 '14 at 20:46
Not the answer to your question, but your algorithm is broken. It will claim that `addOK(0xffffffff, 1)` doesn't have an overflow, when in fact it does. — pat, Sep 23 '14 at 04:58
Are you shooting for signed or unsigned overflow? All of your values are signed, but you're apparently only looking for a carry-out of bit 31, which is not a signed overflow. — pat, Sep 23 '14 at 05:00

score 0 · Answer 1 · answered Sep 23 '14 at 14:49

I tried my code on a Linux 32-bit and there the particular issue stated above did not occur.

I conclude the problem was due to the OS and/or the compiler I was using. Since I didn't write the tests or the makefile myself and am not familiar enough with C so far, I still don't understand exactly what went wrong.

But as pat pointed out (thank you)

Are you shooting for signed or unsigned overflow? All of your values are signed, but you're apparently only looking for a carry-out of bit 31, which is not a signed overflow. -pat

the algorithm I wrote was broken in the first place. I had the wrong idea of the overflow in my mind. I had to check for the signed overflow which occurs when either two negative ints are added and overflow to a positive one or two positive numbers to a negative one. (According to two's complement arithmetic).

If anyone is interested here is my working code:

int addOK(int x, int y) {
    int mask = 1 << 31;   // 0x80000000
    int msbX = mask & x;  // Set all bit to 0 except sign bit
    int msbY = mask & y; 
    int msbSum = mask & (x + y);
    int prob1 = !(msbX ^ msbY);   // == 1 iff x and y have the same sign - thats when an overflow may occur
    int prob2 = !(msbX ^ msbSum); // == 0 iff x + y and x have a different sign - thats when an overfolow may occur
    return (!prob1) | prob2;      // There is an overflow iff prob1 == 1 and prob2 == 0
}

In this code the problem I asked about above doesn't even occur and I'm able to run it directly on my mac again.

Weird behavior of & operator in C

1 Answers1