CODEWITHSUNDEEP
cbinary
satoru
satoru

Reputation: 33215

What does it mean if the bitwise XOR of the sum and two addends are both negative?

For example, there are 3 variables of long type, we add a and b and get s:

long a, b, s;
...
s = a + b

Now what does ((s^a) < 0 && (s^b) < 0) mean?

I saw a check like this in the source code of Python:

    if (PyInt_CheckExact(v) && PyInt_CheckExact(w)) {
        /* INLINE: int + int */
        register long a, b, i;
        a = PyInt_AS_LONG(v);
        b = PyInt_AS_LONG(w);
        i = a + b;
        if ((i^a) < 0 && (i^b) < 0)
            goto slow_iadd;
        x = PyInt_FromLong(i);
    }

Upvotes: 7

Views: 72

Answers (2)

user2357112
user2357112

Reputation: 280291

This code is wrong.

Assuming the usual 2's-complement rules of bitwise XOR for signed integers, then

(s^a) < 0

is the case if s and a have their sign bits set to opposite values. Thus,

((s^a) < 0 && (s^b) < 0)

indicates that s has sign different from both a and b, which must then have equal sign (pretending 0 is positive). If you added two integers of equal sign and got a result of different sign, there must have been an overflow, so this is an overflow check.

If we assume that signed overflow wraps, then s has opposite sign from a and b exactly when overflow has occurred. However, signed overflow is undefined behavior. Computing s is already wrong; we need to check whether the overflow would occur without actually performing the operation.

Python isn't supposed to do this. You can see what it's supposed to do in the Python 2 source code for int.__add__:

/* casts in the line below avoid undefined behaviour on overflow */
x = (long)((unsigned long)a + b);
if ((x^a) >= 0 || (x^b) >= 0)

It's supposed to cast to unsigned to get defined overflow behavior. The cast-to-unsigned fix was introduced in 5 different places as a result of issue 7406 on the Python bug tracker, but it looks like they missed a spot, or perhaps INPLACE_ADD was changed since then. I've left a message on the tracker.

Upvotes: 5

Sam Estep
Sam Estep

Reputation: 13294

I don't see how this is possible.

If (s^a) < 0, then the sign bit of either s or a must be a 1, so either s or a (but not both) must be negative. Same for s and b. So either s is negative and both a and b are positive, or s is positive and both a and b are negative. Both situations seem impossible.

Unless you count integer overflow/underflow, of course.

Upvotes: 2

Related Questions