Integer ranges and two's complement in Python

Why this matters

Every whole-number type in a fixed-size language has a limited range, which is the set of values it can hold. A byte in Java holds 8 bits, an int holds 32 bits and a long holds 64 bits. Pick the wrong size and a value that is perfectly reasonable, such as a bank balance or a pixel position, can silently turn into a different number.

Python is different. Its int has no fixed size, so it grows to hold any whole number that fits in memory. Most of the bugs in this lesson cannot happen in plain Python code. They still matter for three reasons. Fixed-size numbers appear in files, network packets and other languages. The ctypes and array modules give you fixed sizes on purpose. And interviewers ask about these ranges, because the answer shows whether you understand what a number is inside a computer.

This lesson starts with the rule for fixed sizes, shows how two's complement stores negative numbers, and then shows what Python does instead. The floating-point types, such as float, follow different rules, which the floating-point lesson covers.

Python ints have no fixed size

A Python int keeps every digit it needs. The next program shows an addition that would overflow a 32-bit int, and a power that would need 101 bits.

4000000000
1267650600228229401496703205376
<class 'int'>

The sum is 4 billion, and the power has 31 digits. Both are still int. No value wraps around, and no value is cut off. The only limit is the memory of your computer. Because of this, the sections below about wrapping are about fixed-size types, not about the int you use every day.

Fixed-size ranges

A fixed-size type holds a fixed number of bits, and the number of bits sets the range. For a signed type with n bits, the smallest value is minus 2 to the power n - 1, and the largest value is 2 to the power n - 1 minus 1. The function below computes the range for a given number of bits, and the next program prints the ranges of the four common sizes.

8 (-128, 127)
16 (-32768, 32767)
32 (-2147483648, 2147483647)
64 (-9223372036854775808, 9223372036854775807)
sys.maxsize: 9223372036854775807

The value sys.maxsize is the largest value a Python list index or a C-style counter can hold on this machine. On a 64-bit system it is the same as the largest 64-bit signed value. It is useful as a starting value for a search for a minimum, but it is not a limit on Python int values.

How two's complement stores negative numbers

Take an 8-bit value, because 8 bits is small enough to write out. Each bit has a weight, which is the amount that bit adds to the total when it is 1. In two's complement, the leftmost bit, called the sign bit, has a negative weight. From left to right, the weights are -128, 64, 32, 16, 8, 4, 2 and 1.

To read a pattern, add the weights of the bits that are 1. Take the pattern 11111011.

• The leftmost bit is 1, so it adds -128.
• The bits with weights 64, 32, 16, 8 and 2 and 1 are 1, and the bit with weight 4 is 0. These add 64 + 32 + 16 + 8 + 2 + 1, which is 123.
• The total is -128 + 123, which is -5.

So 11111011 means -5. The pattern 00000101 means 5. The program below shows the 8-bit pattern of a few values. The & 0xFF keeps the lowest 8 bits. Python treats a negative number as if it had an infinite row of 1 bits at the left, so the mask is how you ask for the 8-bit pattern.

00000101
11111011
10000000
01111111

The last two lines show the range edges. The pattern 10000000 is -128, because only the sign bit is 1. The pattern 01111111 is 127, because every bit except the sign bit is 1, and their weights add to 127. Nothing lies beyond these two patterns, which is why the range ends at 127 on the positive side and at -128 on the negative side.

The function int.from_bytes reads a pattern as a signed number, so you can check the weight sum:

-5
5

Why the negative side is one bigger

Count the patterns. There are 256 of them in 8 bits. The first half, with the sign bit 0, covers the values 0 up to 127. That is 128 values. The second half, with the sign bit 1, covers the values -128 up to -1. That is also 128 values. Zero uses one of the 128 patterns in the first half, so the positive side has only 127 numbers above zero. The negative side has all 128 of its numbers.

So the range is not symmetric. An 8-bit value can hold -128 but cannot hold 128. A 32-bit value can hold -2147483648 but cannot hold 2147483648. The ctypes module shows this. The c_int8 type is an 8-bit signed value:

-128
127
-128

The third line does not raise an error. The value 128 does not fit, so c_int8 keeps the low 8 bits, and those bits read as -128. The next section explains that wrap.

Overflow at the top of a fixed-size range

When the result of an operation is past the largest value of a fixed-size type, the result wraps. The value goes past 127 and comes back at -128. Nothing stops the program and nothing warns you.

-128
-294967296

The first result is the 8-bit wrap. The pattern 01111111 plus 1 is 10000000, which reads as -128. The second result is the 32-bit version of the total from the previous lesson. The true sum is 4000000000, which does not fit in 32 bits, so the bits wrap to -294967296.

Plain Python int does not do this. The same addition gives the exact value, as the first section showed. The wrap happens only when you store the value in a ctypes type, or in another language.

Negating the smallest value in a fixed size

Negation turns 5 into -5 and -5 into 5. In two's complement, you negate a number by flipping every bit and adding 1. On the smallest 8-bit value, -128, the flip gives 01111111, and adding 1 gives 10000000 again. The result is -128. The true answer, 128, does not fit in 8 bits, so the bits wrap back to the smallest value.

-128
128

The first line shows the fixed-size answer, which stays negative. The second line uses a plain Python int, which has no fixed range, so the negation is exactly 128. The same is true for absolute values. In Java, Math.abs of the smallest int returns a negative number. In Python, abs(-2147483648) returns 2147483648.

Hex and the bits of the limits

Hexadecimal, which is base 16, shows 32 bits in eight digits, so it is a common way to show the limits of a 32-bit type. The smallest 32-bit value is a 1 followed by 31 zeros, which is 80000000 in hex. The largest is 31 ones, which is 7fffffff.

80000000
7fffffff

The mask & 0xFFFFFFFF keeps the 32 low bits of the negative value. The top digit of 80000000 is the sign bit.

Worked example: does a value fit?

A common task is to check a number before you store it in a smaller type. Suppose a program reads a score and must keep it in an 8-bit signed field. The check has to compare the number with the real limits of the type. It must not assume the limits are symmetric.

The program below has two checks. The first compares the value with the limits from the range formula. The second stores the value in a ctypes type and compares the result with the original. If the stored value is unchanged, it fits. If bits were cut off, the two values differ.

127 True True True True
128 False False True True
-128 True True True True
-129 False False True True
3000000000 False False False False

The value 128 does not fit in 8 bits, but it fits in 32 bits, so the 8-bit checks say False and the 32-bit checks say True. The value 3000000000 is past the largest 32-bit value, so both 32-bit checks say False. The two methods agree on every row, and the round trip is the one to use when you are checking a value that will be stored in a ctypes field.

Worked example: sums in a fixed size

A sum of two large values stored in a 32-bit field gives a negative total. The same sum in Python gives the exact answer. The next program adds the two values in a plain int and in a 32-bit field, so you can compare the two results.

Python int sum: 4000000000
32-bit sum:     -294967296

The true total is 4000000000. The 32-bit total wraps past 2147483647 and comes back negative. The fix in Python is to keep the plain int, which holds the exact value. The fix in a fixed-size language is to choose a type by the largest total the program can produce, not by the size of one value.

Common mistakes

Assuming the range is symmetric. A beginner often writes a check such as if x < -127 or x > 127 to test whether a value fits in 8 bits. That rejects -128, which fits. Use -128 <= x <= 127, or the formula in fits_in_bits.

Expecting a Python int to wrap. The sum 2 ** 63 - 1 + 1 is 9223372036854775808 in Python. Code written for a fixed-size language may expect the wrap, and the output differs. Check the type of the value before you assume a limit.

Expecting an error from ctypes. Storing 128 in ctypes.c_int8 does not raise an error. It stores -128. Compare the stored value with the original, as the round-trip check does, when a wrong value would matter.

Using array for a value that is too big. The array module refuses values outside its range, which is a different behaviour from ctypes. The message names the limit:

import array
array.array("b", [128])

Traceback (most recent call last):
  File ".../array.py", line 2, in <module>
    array.array("b", [128])
    ~~~~~~~~~~~^^^^^^^^^^^^
OverflowError: signed char is greater than maximum

Putting a value that is out of range in bytes. The bytes type holds only the values 0 to 255. Passing 256 raises an error:

bytes([256])

Traceback (most recent call last):
  File ".../bytes.py", line 1, in <module>
    bytes([256])
    ~~~~~^^^^^^^
ValueError: bytes must be in range(0, 256)

The fix is to keep each value in the range of the type, or to choose a type with a larger range.

Practice

Work each exercise yourself before you open the answer. Predict the output on paper first.

1. Predict the output of this program, then run it to check. Use ctypes.c_int8 and the value -128, then subtract 1 with .value -= 1 and print the result.
2. Write the 8-bit two's complement pattern for the value 100 with format.
3. Explain why the value -32769 does not fit in a 16-bit signed field, and give the largest and smallest values such a field can hold.
4. Write a function fits_in_bits(value, bits) that returns True when the value fits in the given number of signed bits, and test it with 127, 128 and -129 for 8 bits.
5. What does ctypes.c_int8(200).value print?

Each exercise has an answer below a "Show the answer" line. Try each one first, then read the answer.

1. The output is 127. The pattern 10000000 minus 1 is 01111111, which is the largest 8-bit value. The decrement wraps from the bottom of the range to the top.

Show the answer

import ctypes
 
x = ctypes.c_int8(-128)
x.value -= 1
print(x.value)

The output is 127.

2. The pattern is 01100100. The weights 64, 32 and 4 add up to 100, so those bits are 1 and the others are 0.

Show the answer

print(format(100 & 0xFF, "08b"))

The output is 01100100.

3. The smallest 16-bit signed value is -32768, and the largest is 32767. The value -32769 is one below the smallest, so it does not fit.

Show the answer

print(-(2 ** 15), 2 ** 15 - 1)

The output is -32768 32767, which gives the limits of a 16-bit signed field.

4. The check compares the value with the smallest and largest values for the bit count.

Show the answer

def fits_in_bits(value, bits):
    return -(2 ** (bits - 1)) <= value <= 2 ** (bits - 1) - 1
 
print(fits_in_bits(127, 8))
print(fits_in_bits(128, 8))
print(fits_in_bits(-129, 8))

The output is True, False and False.

5. The value 200 does not fit in 8 signed bits. The low 8 bits of 200 read as 200 minus 256, which is -56.

Show the answer

import ctypes
 
print(ctypes.c_int8(200).value)

The output is -56.

What you now know

• A Python int has no fixed size, so sums and powers stay exact. Fixed-size types appear in ctypes, array, files and other languages.
• A signed type with n bits holds values from minus 2 to the power n - 1 up to 2 to the power n - 1 minus 1.
• In two's complement, the sign bit has a negative weight. A pattern is read by adding the weights of its 1 bits.
• The negative side of each range is one value bigger than the positive side, because zero takes one pattern from the positive half.
• A value past the top of a fixed-size range wraps to the bottom without an error. Check it with a round trip through ctypes, or with the range formula.
• Negating the smallest fixed-size value gives the same value, because the true answer does not fit. Python's plain int gives the exact answer.