sdlc.dev

Computer science fundamentals for working engineers path · How data is stored · Topic 3 of 13

Binary, integers and overflow

Not started

Computers store numbers in binary, base 2, using a fixed number of bits chosen by the type: 8 for a byte, 32 for an int in most languages, 64 for a long. A fixed width means a fixed range. When arithmetic produces a result outside that range, the hardware keeps only the low bits, so the value "wraps around". Whether your language lets that happen silently, raises an error, or treats it as undefined is one of the most important things to know about its integers.

Why it matters: Overflow bugs have crashed rockets, frozen games and broken binary searches. They come from forgetting that most integers have a fixed number of bits.

  1. 1Bits and place value

    Binary is base 2: each bit is worth twice the one to its right. n bits can hold 2ⁿ different values.

  2. 2Two's complement

    Signed integers use the top bit as a large negative weight, so an 8-bit value runs from −128 to 127 and adding works the same for signed and unsigned.

  3. 3Overflow wraps or traps

    In hardware, the result is kept modulo 2ⁿ. Languages either wrap (Java, Go, C# by default), trap (Rust in debug, Swift), or call it undefined (signed ints in C).

  4. 4JavaScript numbers are doubles

    Integers are exact only up to 2⁵³ − 1. Bitwise operators work on 32-bit integers, and BigInt gives arbitrary precision.

1

How it works

The explanation, with examples you can run.

Binary and two's complement

Each bit is worth twice the bit to its right: 0000 0101 is 4 + 1 = 5. Eight bits give 2⁸ = 256 patterns, so an unsigned byte holds 0 to 255.

For negative numbers, almost every CPU uses two's complement: the top bit counts as −2⁷ (−128) instead of +128. So 1000 0000 is −128, 1111 1111 is −1, and the signed range is −128 to 127. To negate a number, flip every bit and add one. The big advantage is that the same adder circuit works for signed and unsigned values; only the interpretation differs.

Typed arrays let you see this directly from JavaScript:

⌘/Ctrl + Enter
OutputNot run yet

Press Run to see what your code prints, in order.

Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

This prints 0, −128 and −2147483648 for the three overflows, then shows −1 as thirty-two 1 bits, and −5 as …11111011. The last line prints 4,3,2,1 on x86 and Arm machines: they are little-endian, storing the least significant byte first. Network protocols traditionally use big-endian ("network byte order"), which is why binary parsers must say which one they expect.

What languages do on overflow

  • Wrap silently: Java, Go, C# (unless you use checked), and unsigned integers in C and C++.
  • Trap: Swift always; Rust in debug builds (release builds wrap unless you enable checks, and checked_add and friends are always available).
  • Undefined behaviour: signed overflow in C and C++. The compiler may assume it never happens and optimise accordingly, so the program can do anything.
  • Grow: Python's int and JavaScript's BigInt have no fixed width, so they never overflow, at the cost of speed.

JavaScript's special case

A JavaScript number is a 64-bit floating-point value (next topic). It represents every integer exactly only up to Number.MAX_SAFE_INTEGER, 2⁵³ − 1 = 9,007,199,254,740,991. Beyond that, 2 ** 53 + 1 evaluates to 9007199254740992. That bites when a 64-bit database id or a Twitter-style snowflake id is parsed from JSON as a number, so such ids are usually sent as strings. Bitwise operators convert to 32-bit integers first, which is why (2 ** 31) | 0 is −2147483648.

Real bugs

The Ariane 5 rocket's first flight in 1996 failed when a 64-bit floating-point value was converted to a 16-bit signed integer that couldn't hold it. Many binary searches, including the one in Java's standard library until 2006, computed (low + high) / 2, which overflows for arrays of over a billion elements. Unix time stored in a signed 32-bit integer runs out on 19 January 2038, a topic in the time chapter.

2

Check yourself

3 questions. Get them all right to finish this topic.

  1. 1.An Int8Array holds 127. What is it after adding 1?
  2. 2.What is the classic overflow bug in `mid = (low + high) / 2` with 32-bit ints?
  3. 3.In JavaScript, what is 2 ** 53 + 1?

0 of 3 right so far. Get all three to finish this topic.

Go deeper