Python Bitwise Operators on Arbitrary-Precision Integers

Python supports arbitrary-precision integers, meaning numbers can grow as large as available memory allows without suffering from integer overflow. When applying bitwise operators such as XOR (^), AND (&), OR (|), and bit-shifts (<<, >>), Python does not use fixed-width 32-bit or 64-bit registers. Instead, it computes results by simulating a conceptually infinite two's complement binary representation, dynamically allocating memory for the resulting digits.

The Infinite Two's Complement Model

In languages like C, bitwise operations manipulate fixed-size memory registers. If you perform a bitwise NOT or shift beyond 64 bits, bits fall off the edge or wrap around.

Python avoids fixed boundaries by conceptualizing integers as having an infinite number of sign bits extending to the left:

• Positive integers are treated as having an infinite sequence of leading 0 bits (...00000000[bits]).
• Negative integers are treated as having an infinite sequence of leading 1 bits (...11111111[bits]), matching standard two's complement arithmetic.

This conceptual model ensures that operations like ~x (bitwise NOT) yield mathematically consistent results: ~x is always equal to -x - 1.

How Python Handles XOR (^)

Bitwise XOR returns 1 where the bits of two operands differ, and 0 where they match.

• Two Positive Integers: Python iterates through the internal representation of both numbers limb by limb (typically 30-bit digits in CPython), XORing matching limbs. The resulting integer terminates when the highest set bit of the larger operand is reached.
• Positive and Negative Integers: Because the negative integer conceptually has infinite leading 1s and the positive integer has infinite leading 0s, the infinite leading bits XOR to 1 (0 ^ 1 = 1). Consequently, the result is negative.
• Two Negative Integers: The infinite leading 1s XOR against each other to produce infinite leading 0s (1 ^ 1 = 0), which always yields a positive result.

How Python Handles Bit-Shifting

Bit-shifting adjusts the magnitude of the integer while adjusting the underlying memory layout:

Left Shift (<<)

Left-shifting a number by n places (x << n) is mathematically equivalent to multiplying by \(2^n\).

• Python allocates a new integer object with enough extra 30-bit limbs to hold the shifted value.
• The original bits are shifted, and n zero bits are inserted at the least significant positions.
• Because precision is arbitrary, left-shifting never causes an overflow error; it simply consumes more RAM as the number expands.

Right Shift (>>)

Right-shifting a number by n places (x >> n) performs an arithmetic right shift, equivalent to floor division by \(2^n\) (floor(x / 2**n)).

• For positive numbers, the lowest n bits are discarded, and the digit array shrinks as needed.
• For negative numbers, because of the conceptual infinite stream of leading 1 bits, sign extension preserves the negative sign. For example, -1 >> 5 results in -1, because an infinite sequence of 1s shifted to the right remains an infinite sequence of 1s.

CPython's Internal Mechanism

Under the hood, CPython's int structure (PyLongObject) stores integers using a sign-magnitude representation rather than native two's complement. It holds an array of unsigned digits paired with a separate sign indicator.

To execute bitwise operations correctly:

1. CPython converts negative operands from sign-magnitude into an on-the-fly two's complement format.
2. It processes the digits sequentially starting from the least significant digit up to the size of the larger operand.
3. Once the bitwise logic finishes, CPython normalizes the output back into its native sign-magnitude format, stripping away redundant leading digits.