What does it mean that the bitwise XOR sums and two terms are negative?

Question

For example, there are 3 variables of a 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 this check in the Python source code :

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

Answer 1

This code is invalid.

Assuming the usual rules of the 2nd complement for bitwise XOR for signed integers, then

 (s^a) < 0 

- this is the case if s and a have signed bits set to opposite values. Thus,

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

indicates that s has a sign different from both a and b , which should have an equal sign (pretending to be 0 is positive). If you add two equal signs and get the result of a different sign, there must be an overflow, so this is an overflow check.

If we assume that the signed overflow wrappers, then s has the opposite sign from a and b exactly when the overflow occurred. However, the signed overflow is undefined. The calculation of s already incorrect; we need to check if an overflow will occur without actually performing the operation.

Python should not do this. You can see what it should 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 is assumed that it must distinguish between unsigned in order to obtain certain overflow behavior. The cast-to-unsigned fix was introduced in 5 different places as a result of issue 7406 in Python, but it looks like they missed since then the location has changed, or perhaps INPLACE_ADD . I left a message on the tracker.

Answer 2

I do not see how this is possible.

If (s^a) < 0 , then the sign bit either s or a must be 1, therefore either s or a (but not both) must be negative. The same goes for s and b . Thus, either s negative, and both a and b positive, or s positive, and both a and b negative. Both situations seem impossible.

Unless, of course, you consider overflow / underflow of integers.