Much of the code in Objects/intobject.c assumes that an arithmetic operation on signed longs will wrap modulo 2**(bits_in_long) on overflow. However, signed overflow causes undefined behaviour according to the C standards (e.g., C99 6.5, para. 5), and gcc is known to assume that signed overflow never occurs in correct code, and to make use of this assumption when optimizing. An obvious example is found in int_add, which looks like this: static PyObject * int_add(PyIntObject *v, PyIntObject *w) {	register long a, b, x;	CONVERT_TO_LONG(v, a);	CONVERT_TO_LONG(w, b);	x = a + b;	if ((x^a) >= 0 || (x^b) >= 0)	return PyInt_FromLong(x);	return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w); } Here Python is relying on the line 'x = a + b' wrapping on overflow. While this code doesn't seem to have caused any problems to date, it's not at all inconceivable that some future version of GCC is clever enough to figure out that (with its assumption that correct code never includes signed overflow) the if condition is always false, so can be optimized away. At that point, a Python interpreter built with this version of GCC would produce incorrect results for int addition. More generally, Python's source makes a number of assumptions about integer arithmetic that aren't guaranteed by the C standards. Most of these assumptions are likely to be harmless on modern machines, but the assumptions should probably at least be documented somewhere, and ideally also checked somewhere in the configuration, so that attempts to port Python to machines that don't obey these assumptions complain loudly. Namely, the source assumes at least that: - C signed ints are represented in two's complement, not ones' complement or sign-and-magnitude. - the bit pattern 1000....000 is not a trap representation (so e.g., INT_MIN = -INT_MAX-1, not -INT_MAX). - conversion from an unsigned integer type to the corresponding signed type wraps modulo 2**(appropriate_number_of_bits). (Relevant standard sections: C99 6.2.6.2, C99 6.3.1.3p3.) See also issue 1621.

Fixed int_sub, int_add, int_mul, and the fast paths for BINARY_ADD and BINARY_SUB in ceval.c, in r76629 (trunk) and r76630 (release26-maint).

Here is a way to test for overflow which is correct for any C implementation: static PyObject * int_add(PyIntObject *v, PyIntObject *w) {	register long a, b;	CONVERT_TO_LONG(v, a);	CONVERT_TO_LONG(w, b);	if (((a>0)&&(b>0)&&((LONG_MAX-a)<b))	||((a<0)&&(b<0)&&((LONG_MIN-a)>b))) {	/* would overflow the long type */ return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);	}	return PyInt_FromLong(a+b); }

Here is a set of macros that I use to test for overflow: http://allmydata.org/trac/libzutil/browser/libzutil/zutilimp.h

Zooko: Yes; that's the sort of solution that's needed if we're not allowed to assume two's complement with the extraordinary value (- sys.maxint - 1) not a trap representation. If we are allowed to assume this, then more efficient solutions are available. Also, if we're not allowed to assume two's complement + no trap representation, then int_and, int_xor, int_or are plain wrong: For ones' complement or sign-and-magnitude, the result of these logical operations won't match the result of the corresponding operations on longs, for negative operands. For two's complement with (-sys.maxint-1) a trap representation, int_and and int_xor should be producing a Python long instead of a Python int in some cases: -sys.maxint ^ 1 should be -sys.maxint - 1, which wouldn't be representable as a Python int. That's why I want to make these extra assumptions beyond what's guaranteed by the C standards; working around them introduces inefficiencies for all implementations, for the benefit of implementations that (probably) don't even exist.

I consider the binary bitwise operations, for negative ints, to be either undefined or wrongly implemented. Consider the following (3.1) >>> 3^2 1 >>> -3^2 -1 >>> 3^-2 -3 >>> -3^-2 3 >>> 2^3 1 >>> -2^3 -3 Something change sign just flips the sign of the result, sometimes it also changes the magnitude. From the viewpoint of arithmetic, and signed base-two representations, the latter seems senseless. The doc says only "The ^ operator yields the bitwise XOR (exclusive OR) of its arguments, which must be integers." But it does not define what bitwise XOR means for signed ints, as opposed to unsigned bit strings, possible interpreted as (unsigned) counts, which is the traditional domain of bit-operation definition. So there is no way to predict the result for negative ints. Or rather, the sensible prediction does not match the observed behavior. My impression is that Python longs are signed magnitudes. If so, the bitwise ops should arguably be the signed result of the op on the magnitudes.

Terry, the language reference also says: """ For the purpose of shift and mask operations, a binary representation is assumed, and negative numbers are represented in a variant of 2's complement which gives the illusion of an infinite string of sign bits extending to the left. """ That explains every result you saw: 3 = ...000011 2 = ...000010 1 = ...000001 -3 = ...111101 2 = ...000010 -1 = ...111111 3 = ...000011 -2 = ...111110 -3 = ...111101 -3 = ...111101 -2 = ...111110 3 = ...000011 2 = ...000010 3 = ...000011 1 = ...000001 -2 = ...111110 3 = ...000011 -3 = ...111101 In every case, the result is simply the xor of the inputs viewed as infinite bitstrings. And it works exactly the same way if you use |, &, <<, >>, or unary ~. It's true that CPython's longs are /implemented/ via sign-magnitude, but that should never be visible in the result of any operation.

Thanks Tim. I see that is back in 3.2 rather than in the shift and mask sections. At least I know what to refer to now.

It looks like the fast paths for INPLACE_ADD and INPLACE_SUBTRACT in Python 2 don't have the cast-to-unsigned fix, so they're still relying on undefined behavior. For example, in INPLACE_ADD: /* 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;

Python 2 is no longer supported. Python 3's _PyLong_Add() function doesn't rely on overflow.