Binary & Number Systems Primer

Every layer in this course moves bytes. curl https://api.example.com/user/42 becomes a run of them the moment it leaves the shell, and so does the integer your handler parses out of the path. Eight is not a law of nature: IBM's System/360 fixed it in 1964, and byte-granular tooling made the choice permanent.

Each position carries a power of two, and the value is the sum of the set ones — drag the slider and watch the bits fill in with the two hex digits their nibbles spell:

Notice that the hex digits never argue with the bits: four bits is exactly one hex digit, because 16 = 2⁴, so nothing is hidden in the translation. Decimal has no such property — 255 tells you nothing about which bits are set, while 0xff tells you all eight are.

That is also why every debugger, hex editor and packet capture prints hex rather than decimal. A hex byte is always two columns wide; the same byte in decimal is one, two or three. Drag the cursor along the row:

Watch the decimal row lose its grid. 72, 84 and 47 do not line up, so finding the fourteenth byte means counting characters instead of counting cells. The hex row is a ruler. The whole argument for hex is typographic, and it is a good one.

Bytes carry no type. The character 4 in our URL is not the number four — it is whatever byte ASCII assigns to that glyph, and the slider walks the string one character at a time:

The character 4 is 52, or 0x34; the integer 4 is 0x04. A parser that forgets the difference is off by 48 on every digit, which is exactly why atoi subtracts '0'. These seven bytes are what curl writes for the tail of the path.

ASCII covers 128 codepoints in a single byte with the top bit clear. UTF-8 keeps that byte bit-for-bit identical and buys the rest of Unicode by spending more of them — walk the codepoint up and watch the continuation bytes appear behind the lead byte:

Because the ASCII range is untouched, every ASCII tool survived the web's move to UTF-8 without a line of code. Above 0x7F, the lead byte's high bits announce the length — 110 for two, 1110 for three, 11110 for four — so a decoder never needs a separate length field.

None of that is stored anywhere. A byte in memory carries no tag saying which agreement applies; whichever instruction reads it next decides. Switch the reading and watch four fixed bytes give four unrelated answers:

Notice that the bytes never moved. 42 28 00 00 is the text B( and two NULs, the little-endian integer 10,306, the big-endian 1,109,917,696, and a float32 subnormal near 1.4×10⁻⁴¹. Type is a promise your compiler keeps for you; the hardware makes none.

Storing a positive integer is obvious; storing −42 is the interesting half. Sign-and-magnitude gives the top bit to the sign and ends up with two zeros and four addition cases. One's complement flips every bit and needs an end-around carry cycle. Both lost by the 1970s.

Two's complement takes the modular view instead: eight bits hold a residue modulo 256, and nothing else. The wheel below is that residue class drawn once — drag it round and watch one position carry an unsigned reading and a signed one at the same time:

The wheel has exactly one seam. Clockwise, the unsigned reading counts 0 to 255 without interruption while the signed reading counts 0 to 127 and then drops to −128. The two agree on the lower half and differ by exactly 256 on the upper half. That is the entire definition.

Negation falls out of it. We want −x to satisfy x + (−x) ≡ 0 mod 256, so −x is 256 − x; and 256 − x is "flip every bit, then add one", because flipping gives 255 − x. Step the scrubber and watch the negative get built out of the positive:

The flip on its own is not the answer: ~42 is 213, and 42 + 213 is 255 — one short of the wrap. The +1 closes it. Nothing here is a special negative-number circuit; it is two operations the ALU already has, in the order the algebra demands.

Which means subtraction is not a circuit either. The adder adds eight columns and throws the ninth away, and modulo 256 that is the right answer under both readings — move the two operands and watch the carry leave the register:

Set the operands to 42 and −42 and the columns produce 1 00000000: the carry out is discarded and the register holds zero. Read unsigned, the same columns say 42 + 214 = 256 ≡ 0. One adder, two readings, and no branch on sign anywhere in the datapath.

Two of those columns are worth naming, because the hardware keeps both. The carry out of the top column, c₈, becomes the carry flag CF; the exclusive-or of it with the carry into the top column, c₇, becomes the overflow flag OF. Drive the same adder past 127 and watch which lamp lights:

CF = c₈ says the unsigned reading did not fit; OF = c₈ ⊕ c₇ says the signed one did not. They are independent. 100 + 100 sets OF alone — 200 fits a byte, it just does not fit a signed one. −1 + 1 sets CF alone — 255 + 1 leaves the byte, and the signed answer 0 is still right. −100 + −100 sets both. The adder computes one sum and flags it twice; ADD costs the same either way, because the pair is one XOR gate hanging off a carry chain that had to exist anyway.

Three operations do have to know which reading you meant, and the cheapest to see is the shift. Both versions move the same eight columns; they differ only in what they feed into the vacated top cells — a copy of the sign bit, or zeros. Take x below zero and separate them:

For x ≥ 0 the two agree. At x = −100, k = 3 the arithmetic shift gives −13 and the logical one 19. Only the arithmetic shift is x / 2^k, and it rounds toward −∞, so x >> 1 and x / 2 disagree on every negative odd number.

The invariant worth carrying out: an n-bit register holds a residue class modulo 2ⁿ, and signed and unsigned name two representatives of it. Add, subtract and multiply are one instruction under both; divide, compare and right-shift read the top bit as a sign — and they are the list that goes wrong next.

In eight signed bits the range is −128 to +127: 128 negatives, 127 positives, and zero. The magnitude 128 has no positive twin, so C and C++ make abs(INT_MIN) undefined behaviour. Most implementations return the argument unchanged, and none of them throws.

Flip-and-add-one is a permutation of the 256 patterns, and this permutation has a fixed point — walk x along the axis until its negative stops moving:

At −128 the flip gives 01111111 and the +1 carries all the way back to 10000000, which is where we started. abs hands back a negative number and reports nothing. Whatever is downstream — an array index, a length, a loop bound — now has a negative it was written to assume away.

Overflow on the way up is the same failure with a friendlier reputation. Add sixteen to an int8 accumulator over and over, and the value that fits becomes the value that wrapped the moment the ninth column falls off the end:

At eight additions the sum is 128, the register reads −128, and nothing objects. That is not the hardware being quiet: the adder wraps modulo 256 and sets OF, exactly as §02 showed — the byte that goes missing is the flag, and it goes missing in the language. C has no expression that reads a status bit, so a + b discards it, and the standard goes further and calls signed overflow undefined, which lets the compiler assume i + 1 > i always holds and vectorise on that assumption. Rust's checked_add and __builtin_add_overflow are the same ADD with a branch on the flag the chip already set: the check is a predictable branch, not an extra addition.

The most-quoted instance is an average. (lo + hi) / 2 overflows as soon as lo + hi passes 2³¹ − 1, and the axis below is the full width of a signed 32-bit integer — drag hi to the right:

Watch the naive midpoint cross zero and land in the negative half while both indices are still perfectly ordinary. lo + (hi − lo) / 2 never leaves the interval, because it never forms the large sum at all. Joshua Bloch found this in the JDK's own binary search in 2006, nine years after it shipped.

Time is an integer too. A Unix time_t is a signed 32-bit count of seconds since 1970-01-01, and the axis below is that count with the pixels proportional to it — drag the clock forward:

The last second it can name is 2038-01-19 03:14:07 UTC. One second later the counter reads −2,147,483,648 and the same code prints 1901-12-13. Every column, log format and wire field still storing a 32-bit time_t carries that date inside it.

The last trap needs no overflow at all. C's usual arithmetic conversions promote the signed operand to unsigned when the two meet in a comparison, so the comparison happens on an axis you did not choose — move x below zero:

int x = −1; if (x < 1u) is false, because x became 4,294,967,295 — the figure's own axis. Against a size_t the promotion is to whatever width that type has: 32 bits on a 32-bit target, and 64 on every LP64 machine you are likely to be on, where the same x compares as 18,446,744,073,709,551,615. The width changes; the inversion does not. Every guard written that way is backwards. size_t — from strlen, from vector::size() — is almost always the unsigned half, compilers warn on the explicit cases and miss most implicit ones, and the result compiles clean and ships.

Float32 splits its word 1 + 8 + 23; float64 splits 1 + 11 + 52. Both mean the same sentence: value = (−1)^s × 1.m × 2^{e − bias}, with the bias 127 and 1023 respectively.

The three fields sit in that order and are contiguous, and the order is not an accident — walk the bit index across the word and watch which field each bit belongs to:

Notice that the exponent sits above the mantissa. Ignore the sign bit and two positive floats compare in exactly the order their bit patterns do as unsigned integers, so the integer comparator serves both — which mattered for silicon in 1985 and still lets you radix-sort an array of floats today.

The leading 1 of 1.m is never stored. Every normal value has one by definition, so the standard reclaims that bit and gets a free digit — build a value out of its exponent and its mantissa and read the formula off the bottom of the stage:

So twenty-three stored mantissa bits buy twenty-four bits of significand, about 7.2 decimal digits. Float64's fifty-two buy fifty-three, about 15.9. That number — 53 bits — is the one to carry forward; every result in the next section falls out of it.

The exponent is stored biased rather than as a signed field, and the two axes below share their tick spacing so the shift is visible as a shift and nothing else:

Because the stored form is a plain unsigned byte, a larger exponent is a larger bit pattern, with no sign-magnitude discontinuity in the middle to break the ordering. The price is two reserved codes: 0 and 255 name no power of two at all.

Those two codes are where the rest of the number system lives. Switch between the five encodings and watch the reserved exponents claim their ends of the range:

NaN is the one that bites. NaN == NaN is false in every conforming language, which is why x != x is the portable test and why a NaN inside a sort comparator can leave the array unsorted — the comparator stops being a strict weak ordering. Subnormals fill the gap between zero and the smallest normal value, and they are not free: on Sandy Bridge-class Intel cores a subnormal operand or result traps to a microcode assist that Agner Fog's measurements put at roughly 150 clock cycles, against a 5-cycle latency for a normal mulps. Skylake and later removed the penalty for many cases but not all, which is why audio and DSP code still sets the FTZ and DAZ flags and pays for a denormal with a flush to zero instead.

What the whole arrangement buys is reach. Put float32 and int32 on one logarithmic axis of magnitude and drag across it:

Both are 32 bits. int32 reaches 2.1×10⁹ and every integer below it is exact; float32 is still holding a value at 10³⁸, and almost none of the values in between are exact. That is the trade, stated once: the same budget spent on reach instead of on resolution.

The budget is worth counting, because it is the whole subject. Thirty-two bits name 2³² ≈ 4.29×10⁹ distinct values and not one more, whatever you call them. int32 spends the whole budget on one contiguous run, so its values sit 1 apart everywhere. float32 spends 2²³ of them inside each of its 254 normal binades — walk the binades and watch the two counts cross:

Because float32's count is flat and int32's doubles every step, they meet at exactly one place: 2²³, where both hold 8,388,608 values in the same interval, spaced 1 apart. One binade higher, at 2²⁴, float32 has the same 8.4 million to spend over twice the interval, so its spacing is 2 and the odd integers stop existing. That is §07’s whole ladder, derived by counting.

One tenth in binary is 0.000110011001100… repeating forever, the same way one third is 0.333… in decimal. A format with 53 significand bits keeps 53 of those digits and rounds away the rest, once, on the way in.

Pick a fraction and add its binary digits one at a time. The bar underneath is what is still missing, on a logarithmic scale because it halves at every digit:

0.5, 0.25 and 0.75 terminate, because their denominators are powers of two. Twenty-four digits of 0.1 are still short, and so are fifty-three — the stored double is 0.1000000000000000055511151231257827, high by 5.55×10⁻¹⁸.

Two of those roundings plus one more make the most famous line in the subject. Step through it and watch each bar's distance from the decimal it was written as:

The stored 0.1 is high; the stored 0.2 is high; their exact sum is 1.67×10⁻¹⁷ above three tenths, and rounding that sum to a double pushes it to 4.44×10⁻¹⁷ above. The double nearest 0.3 sits 1.11×10⁻¹⁷ below. The two land one ULP apart, and 0.1 + 0.2 == 0.3 is false in every IEEE-754 language for that reason and no other.

That ULP is not a constant. Doubles cluster near zero and spread out away from it, doubling their spacing at every power of two — drag along the curve and read the gap at each magnitude:

At 1 the gap is 2.22×10⁻¹⁶; at 10¹⁶ it is 2. Above that magnitude neighbouring doubles are further apart than neighbouring integers, so most integers up there simply do not exist as doubles.

The crossing has a name and an exact value. Below 2⁵³ every integer is a double; at and above it the significand has run out of room — walk the exponent up and watch the mantissa bits in use reach the end of the row:

At 2⁵³ = 9,007,199,254,740,992, n + 1 === n becomes true and stays true, because the significand has no bit left for the one. JavaScript stores every number as a double, so that is exactly Number.MAX_SAFE_INTEGER + 1 — the reason BigInt was added to the language, and the reason an API that returns 64-bit ids as JSON numbers hands back a different id than it stored.

The last cost is accumulation. Each addition rounds, and the errors in a loop do not cancel — add one cent a thousand times and watch the running error wander:

The error is not monotone and not bounded by any single rounding: it walks. A thousand additions of 0.01 land 1.69×10⁻¹³ short of ten. That is nothing on a dashboard and a reconciliation failure on a ledger — which is why money is stored as an integer count of the smallest unit, or in a decimal type, and never in a double.

Little-endian puts the least-significant byte at the lowest address: x86, x86-64, ARM in its default configuration, Apple Silicon, RISC-V. Big-endian puts the most-significant there: PowerPC, SPARC, IBM mainframes — and every standard network protocol.

Write 0x12345678 across four consecutive addresses and switch the order, watching where the least-significant byte and the most-significant byte land:

Notice that only the addresses changed; the value did not. A CPU reading its own memory never sees a byte order at all — the order is only visible from outside the machine, which is precisely where a hex dump, a packet capture and a file on disk stand.

Little-endian has one concrete argument in its favour: narrowing a value costs nothing, because the low bytes are already at the front. Read the same address one, two and four bytes wide:

A one-byte load at the little-endian address gives 0x78, which is the value modulo 256 — a free truncation. The same load on the big-endian layout gives 0x12, which is not a truncation of anything: to narrow, the reader has to know the original width and add an offset. Multi-precision carries flow low-to-high for the same reason.

Big-endian's argument is that it went first. ARPANET's hosts were mostly big-endian, so IP, TCP, UDP and DNS froze it into their headers, and every multi-byte field still travels that way:

ntohs and ntohl are that swap. On a big-endian host they compile to nothing at all; on x86 they are a single bswap, one instruction with a one-cycle latency. The fixed TCP header is twenty bytes, of which eighteen are multi-byte integers — two ports, two thirty-two-bit sequence numbers, the window, the checksum and the urgent pointer — and the kernel swaps every one of them on every segment in both directions. The nineteenth and twentieth bytes are the data offset and the flag bits, which are read as a word but are not a number.

The failure mode is why this section exists. Point a little-endian reader at big-endian bytes and step through some values:

Most values garble loudly: 305,419,896 arrives as 2,018,915,346. But at 0x12121212, and at zero, and at 0x7f7f7f7f, the swap is invisible and both readings agree. A byte-order bug therefore passes any test suite whose fixtures are small or palindromic — which is most fixtures — and fails on the first real value in production. That is why every binary format worth using writes its endianness into the spec: PNG and ELF and TIFF and WAV all do.

The question a width answers is not "how big" but how big without lying. An integer type reaches exactly as far as it is exact; a float reaches vastly further than it is exact, and the gap between those two numbers is where the bugs live.

The ladder below is logarithmic in the largest integer each width holds exactly — walk the width up it and read the reach off the right-hand end:

Notice where float32 falls: it holds integers exactly only to 2²⁴ = 16,777,216, below int32, though it reaches 10²⁹ further. A 32-bit float is a worse integer than a 32-bit int by a factor of 128, at identical size.

Four lines generate everything on this page. The first two produce abs(INT_MIN), the wrap, the signed-against-unsigned comparison and the overflowing midpoint; the last two produce 0.1 + 0.2, the growing ULP and MAX_SAFE_INTEGER:

n bits hold a residue mod 2^n
bit n-1 set: signed = unsigned-2^n
float = (-1)^s x 1.m x 2^(e-bias)
exact ints: 2^24 f32, 2^53 f64

The ladder is also a test you can run. One convention throughout: a width leaves the exact range at the first power of two it can no longer name every integer below. Drag the magnitude across it and float32 leaves at 2²⁵ — the step above the 2²⁴ its 24-bit significand reaches — while int32, the same 32 bits, leaves at 2³¹:

Watch float32 turn six powers of two before int32 does. The stub past the bar is how far that width is lying by, on the bar’s own log₂ scale. float64 joins at 2⁵⁴, int64 at 2⁶³, and by 2⁶⁴ nothing here is exact.

• == on a float. It asks whether two roundings agreed. Compare against a tolerance scaled to the magnitudes, or in ULPs.
• abs(x) on a value from outside. Undefined at INT_MIN, and it returns a negative rather than throwing. Widen first.
• A signed value against a size_t. i < v.size() promotes the signed i, so a negative counter compares as the largest value of the unsigned type — four billion against a 32-bit unsigned, 1.8×10¹⁹ against an LP64 size_t.
• Money in a double. Store an integer count of the smallest unit; loop errors accumulate.
• fread into a struct with multi-byte fields. It succeeds and returns nonsense across byte orders.

None of these are exotic: each compiles clean, throws nothing, and returns a number.