Number Systems & Binary Arithmetic

Why digital circuits count in binary

A transistor is reliable at telling two voltage states apart – roughly "high" and roughly "low" – but it is not reliable at telling ten apart. Build a circuit that has to distinguish 0 V from 1 V from 2 V, all the way to 9 V, and a small amount of noise on the wire turns a 4 into a 5. Build a circuit that only has to tell "above half the supply" from "below half the supply," and the same noise does nothing. That one fact is the whole reason a digital system represents numbers in base 2 rather than base 10: two states are cheap and robust to build in silicon, ten are not.

Once that is accepted, binary is just another positional number system, the same kind already used every day in decimal. This lesson asks three practical questions about it: how do we convert between bases, how does a circuit add and subtract in binary, and how is a negative number represented when there is no wire set aside for a minus sign?

Positional number systems

In decimal, the number 437 means 4×10² + 3×10¹ + 7×10⁰, or more plainly, 437 = 4×100 + 3×10 + 7×1. Each digit's contribution is its face value multiplied by a weight, and the weight is a power of the base (also called the radix) set by the digit's position. Decimal uses base 10 because people have ten fingers; nothing about the idea itself requires base 10.

A number in any base r with digits dn-1 dn-2 … d1 d0 has the value given by the general positional formula:

Set r to 2 and this is binary, with only two digits available per position: 0 and 1. Set r to 8 and it is octal (digits 0–7). Set r to 16 and it is hexadecimal (digits 0–9, then A–F standing in for 10–15, since a single hex digit needs a single symbol). The formula itself never changes; only r and the digit alphabet do. Thus, every base conversion in this lesson is one formula applied four different ways, not four separate ideas.

Binary to decimal

To read a binary number's decimal value, line the bits up against their weights and add the weights wherever the bit is 1.

Decimal to binary: repeated division

Converting the other way, divide the decimal number by 2 repeatedly and write down each remainder. The remainders, read from last to first, are the binary digits. Let us convert 181 this way and confirm it matches the number used above.

Reading the remainder column from bottom to top gives 10110101, matching the figure above. The same repeated-division method works for any target base: divide by 8 for octal, by 16 for hex, writing a hex digit as A–F whenever a remainder works out to 10–15.

Octal and hexadecimal: grouping bits

Octal and hex exist for one practical reason, and it has nothing to do with how the hardware works. A person reading a 32-bit register dump finds 10110101001011110000111100000011 almost impossible to scan, while the same value written as B52F0F03 in hex stays manageable. The conversion is mechanical because 8 = 2³ and 16 = 2⁴: group the binary digits into sets of 3 (for octal) or 4 (for hex), working outward from the binary point, and convert each group independently of the others.

Binary addition and subtraction

Binary addition follows the same carry logic decimal addition does, just with a much shorter rule table, since there are only four possible bit-pairs to add:

Subtraction has its own borrow rule, but in practice almost no digital circuit implements a separate subtractor for it. Instead, the circuit negates the second number and adds – which is precisely why signed representation matters, and is the subject of the next section.

Representing negative numbers

Decimal has a minus sign available whenever it is needed. A binary word has no spare symbol for "negative" – every bit is already either 0 or 1 – so the hardware has to spend one of the bits on the sign and define exactly what the remaining bits mean once it has. Three schemes have been tried historically, and it is worth seeing why two of them lost.

Sign-magnitude

The top bit is 0 for positive, 1 for negative; the rest of the bits are the ordinary magnitude. This is simple to read by eye, but it has two representations of zero (00000000 and 10000000), and addition has to inspect the sign bits first and branch into either an adder or a subtractor depending on what it finds. It is essentially unused in modern hardware for exactly that reason.

One's complement

Negate a number by flipping every bit. 00000101 (5) becomes 11111010 (−5). This is better than sign-magnitude for arithmetic, but it still has two zeros (00000000 and 11111111), and addition needs an extra "end-around carry" correction step to come out right.

Two's complement: the one everyone actually uses

Negate a number by flipping every bit and then adding 1. That single extra step removes both problems above at once: there is exactly one representation of zero, and – the real payoff – an adder that only knows how to add can also subtract, because A − B is computed as A + (two's complement of B). An adder/subtractor built this way needs nothing more than one adder, a set of inverters on the B input, and a control signal that also feeds the adder's carry-in; this is how essentially every ALU does it.

In an n-bit two's-complement word, the top bit carries a negative weight: an n-bit number ranges from −2n−1 to 2n−1−1. For 8 bits that is −128 to 127, one more negative value than positive, because zero itself uses up one of the slots that would otherwise go to a positive number.

Overflow

Because the word width is fixed, adding two representable numbers can still produce a result that is not representable. The reliable check is this: overflow has occurred exactly when the carry into the sign bit differs from the carry out of the sign bit. The hardware already computes both carries as part of the addition, so detecting overflow costs a single XOR gate, not a second adder.

Binary codes met again later

Not every binary pattern used in hardware is a two's-complement number. Two codes are worth naming here, since later lessons build on them directly.

BCD (binary-coded decimal)

BCD encodes each decimal digit separately in 4 bits (0000–1001; the patterns 1010–1111 go unused). 47 in BCD is 0100 0111 – two 4-bit groups, each simply the ordinary binary value of that one decimal digit. BCD trades density (it needs more bits than pure binary for the same decimal value) for the ability to display or print a number without a binary-to-decimal conversion step, which is why calculator and instrumentation displays have historically used it.

Gray code

An ordinary binary count changes more than one bit at a time at many transitions: 3 (011) to 4 (100) flips all three bits together. In real hardware, bits never flip at exactly the same instant, so a circuit sampling that transition can briefly see an invalid intermediate value. Gray code reorders the same 2n patterns so that every step changes exactly one bit:

Gray code resurfaces in two quite different places later on: in counters built to cross clock domains safely, where a synchronizer only has to sample one changing bit rather than several, and in the row and column ordering of a Karnaugh map, which the next lesson but one covers. A K-map is arranged in Gray-code order for exactly the reason just given here – so that any two side-by-side cells differ in only one variable.