Binary, integers and overflow

To a computer, every value is a sequence of bits: a number, a name, a timestamp. A number has a fixed size, which means it has a fixed range. Once a value grows past that range, it does not fail politely. It wraps around and becomes a small or negative number, often without any error.

The big idea

An unsigned integer of n bits holds the values 0 to 2^n − 1. Here are the common sizes.

Signed integers use two's complement. The top bit has a negative weight. In 8 bits, 1000 0000 is −128, and 1111 1111 is −1. The CPU uses the same adder for signed and unsigned numbers, which is why this scheme won.

Walking through a negative number

To negate a number in two's complement, flip every bit and add 1. Here is −5.

 5       = 0000 0101
~5       = 1111 1010     (flip every bit)
+ 1      = 1111 1011     = −5
check    = −128 + 64 + 32 + 16 + 8 + 2 + 1 = −5

Walking through overflow

Now add 1 to the largest signed 8-bit value, 127.

127 in int8  = 0111 1111
+ 1          = 0000 0001
result       = 1000 0000  = −128

The result wrapped from the top of the range to the bottom. This is integer overflow, and nothing in the CPU stops it. What happens next depends on the language:

• Java and Go wrap silently.
• Rust panics in debug builds and wraps in release builds, unless you use checked_add.
• C and C++ treat signed overflow as undefined. The optimizer may assume it never happens and delete your overflow checks.
• Python integers never overflow. The problem moves to whatever stores the number next.

Real incidents

• YouTube view counter (2014). The count was a signed 32-bit integer. As PSY's "Gangnam Style" video approached 2,147,483,647 views, YouTube moved the counter to 64 bits. Counters that grow with users should be 64-bit from the start.
• Boeing 787 (2015). A counter in the generator control units counted in hundredths of a second and would overflow after 248 days. Check the arithmetic: 2^31 / 100 / 86,400 ≈ 248.6 days. The FAA ordered operators to power-cycle the aircraft periodically.
• Auto-increment keys. A table with 32-bit INT primary keys runs out at about 2.1 billion. Inserts then start failing. Migrating a hot table to BIGINT under load is a slow project. Default to 64-bit IDs.
• Y2038. Unix time stored as a signed 32-bit count of seconds overflows at 03:14:07 UTC on 19 January 2038. Modern 64-bit systems are safe, but embedded devices and some 32-bit database columns still carry the bug.

Endianness: byte order

A 32-bit integer takes 4 bytes, and machines disagree about which byte comes first. Big-endian stores the most significant byte first. Little-endian stores the least significant byte first.

value 0x12345678
big-endian bytes:     12 34 56 78
little-endian bytes:  78 56 34 12

Most servers and phones use little-endian CPUs. Network protocols use big-endian, which is called network byte order. You only meet this when you read raw binary, such as a file format or a network header. Text formats like JSON don't have the problem.

import struct

struct.pack(">I", 1)                        # b'\x00\x00\x00\x01' (big-endian)
struct.pack("<I", 1)                        # b'\x01\x00\x00\x00' (little-endian)
struct.unpack("<I", struct.pack(">I", 1))[0]  # 16777216, the bug

The last line writes 1 big-endian and reads it little-endian. The bytes 00 00 00 01 read as 0x01000000, which is 16,777,216.

Common mistakes

• Using 32-bit counters or IDs for things that grow with usage.
• Assuming overflow raises an error. In most languages it does not.
• Sending 64-bit IDs as JavaScript numbers. Precision silently drops above 2^53.
• Reading binary without naming the byte order. Specify it in the code and in the format spec.

Check yourself

1. What is the value of 1111 1111 as an int8? −1. The top bit has weight −128, and the other bits add 127.
2. A counter stored as int32 grows past 2,147,483,647. What value do you see next? −2,147,483,648, because the value wraps to the bottom of the range.

Key takeaways

• A fixed-size integer has a fixed range. Going past the top wraps to the bottom, often silently.
• Two's complement stores negative numbers. Negate by flipping bits and adding 1.
• Default to 64-bit for counters and IDs. Remember JavaScript numbers are exact only up to 2^53 − 1.
• Byte order only matters for raw binary. Network order is big-endian; most CPUs are little-endian.

Further learning

Next, the hub page numbers, text and encodings shows how these integers combine with floats, text and time. Then read floating point and money for the numbers that are not whole.