Integer

In C and many other languages an integer is a fixed 4 or 8 bytes, and going past $2^{63}-1$ overflows. A Python int is a full object that grows as needed, so it never overflows (until you run out of memory). That convenience has costs in memory and speed, and a few behaviours that trip people up in interviews.

How an int is stored#

CPython stores an int as a PyLongObject. Roughly:

struct PyLongObject {
    Py_ssize_t   ob_refcnt;   // reference count
    PyTypeObject *ob_type;    // points to the int type
    Py_ssize_t   ob_size;     // digit count (also holds the sign)
    digit        ob_digit[1]; // the digits, least significant first
};

(Python 3.12 packs size and sign into one tag field, but the idea is the same.)

The number lives in ob_digit as an array of "super-digits" in base $2^{30}$ on 64-bit builds. Each digit holds a value from 0 up to about one billion.

Big numbers just use a longer digit array. That is the whole trick behind "no overflow".

The small-integer cache#

Creating an object for every 0, 1 or -1 would be wasteful, so CPython creates the integers -5 to 256 once at startup and reuses them.

a = 256
b = 256
print(a is b)                  # True: both point at the cached 256

c = int("257")                 # built at runtime, outside the cache
d = int("257")
print(c is d)                  # False: two separate objects
print(c == d)                  # True: same value

Since Python 3.12, cached ints are "immortal": their refcount is never decremented, so they are never freed.

Ints are immutable#

You can't change an int object. Arithmetic always produces a result object, and the name moves to it.

x = 1789
before = id(x)
x = x + 1
print(id(x) == before)   # False: x now names a different object

What x = x + 1 does:

1. Read the C value out of the 1789 object and add 1 (plain C arithmetic).
2. If the result is in -5..256, return the cached object. Otherwise allocate a new int object holding 1790.
3. Point x at the result.
4. Decrement the old object's refcount. If nothing else uses 1789, it is freed.

What ints cost#

Memory. A small int takes about 28 bytes (header + size + one digit), versus 4 bytes in C.

import sys
print(sys.getsizeof(1))        # 28 on a typical 64-bit build
print(sys.getsizeof(2**30))    # 32: needs a second digit

A list of one million distinct large ints is roughly 28 MB of int objects plus 8 MB of list pointers, not the 4 MB you'd expect in C. If memory matters, array.array('i', ...) stores raw C ints.

Time. Operations on small ints are effectively $O(1)$. On huge ints they scale with the number of digits $d$:

So "arithmetic is $O(1)$" is a fair assumption in interviews only while numbers stay bounded.

Interview gotchas#

Integer behaviour that differs from other languages often shows up in interview edge cases.

# Floor division and modulo round toward negative infinity
print(-7 // 2)        # -4 (C gives -3)
print(int(-7 / 2))    # -3: truncates toward zero ("Evaluate RPN")
print(-7 % 3)         # 2: result takes the sign of the divisor

# bool is a subclass of int
print(True + True, isinstance(True, int))   # 2 True

# Negative numbers act like infinite two's complement
print(-1 >> 1)        # -1: right shift never reaches 0
MASK = 0xFFFFFFFF     # simulate 32-bit ints in bit problems
print((-1) & MASK)    # 4294967295

# Handy built-ins
print(int("101", 2), bin(5))    # 5 '0b101'
print((5).bit_count())          # 2 (bit_count needs 3.10+)
print(float("inf") > 10**100)   # True: a safe "infinity" sentinel

• No overflow means you never need max-int overflow checks, but problems that say "assume 32-bit integers" (e.g. Reverse Integer) expect you to clamp yourself.
• Bit tricks with negatives need a mask, since Python has no fixed width.
• Use math.isqrt(n) for exact integer square roots instead of int(n ** 0.5), which can be off by one for large n.

Key takeaways#

• A Python int is an object holding an array of base-$2^{30}$ digits, so it never overflows.
• -5 to 256 are cached singletons; compare numbers with ==, not is.
• Ints are immutable: every arithmetic result is a (possibly cached) different object.
• Each int costs about 28 bytes, and big-number arithmetic scales with digit count.
• // and % floor toward negative infinity, and bool is an int.