Binary arithmetic and codes

Lesson 1 showed how bit patterns represent unsigned numbers. Real systems also need negative numbers, decimal digits for displays, characters for text, and special codes for sensors and error detection. This lesson covers binary addition and subtraction, the signed number formats used in hardware, overflow, and the standard codes a digital designer meets every week: binary-coded decimal, Gray code, ASCII and Unicode, and parity. Each is a choice of how to map meaning onto bits, and each was invented to make some circuit simpler or more reliable.

Binary addition

Binary addition works exactly like decimal addition, column by column from the right, but with only two digits. The rules are short: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 10, which is a sum bit of 0 with a carry of 1 into the next column. With a carry coming in, 1 + 1 + 1 = 11, a sum bit of 1 and a carry of 1. Lesson 7 builds circuits that do exactly this, one column at a time.

In a fixed-width register, a carry out of the most significant column has nowhere to go. For unsigned numbers this carry is the overflow signal: if it is 1, the true sum did not fit. Adding 200 and 100 in 8 bits gives 300 − 256 = 44 with a carry out of 1. Processors keep this carry in a status flag so that software can detect the overflow or chain several additions together to handle wider numbers.

Representing negative numbers

There are three classic ways to represent signed integers in n bits. All three use the most significant bit as an indication of sign, 0 for positive and 1 for negative, and all three represent positive numbers in the same way as unsigned binary. They differ in how they represent negative numbers.

In sign-magnitude form, the MSB is the sign and the remaining bits are the size of the number, just as people write −5. It is easy to read, but it has two zeros (+0 and −0), and addition circuits must compare signs and magnitudes before they know whether to add or subtract. It survives in floating-point numbers, where the sign is stored separately.

In ones' complement form, a negative number is formed by inverting every bit of the positive number. It also has two zeros, and addition needs an end-around carry. It is now mostly of historical interest, although the internet checksum still uses ones' complement arithmetic.

In two's complement form, a negative number is formed by inverting every bit and adding 1. Equivalently, the MSB of an n-bit number has a weight of −2ⁿ⁻¹ instead of +2ⁿ⁻¹, and all other bits keep their usual positive weights. Two's complement has a single zero, and, most importantly, ordinary binary addition gives the right answer for any mix of positive and negative numbers. That is why virtually every processor and digital signal processor uses it.

An n-bit two's complement number ranges from −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1. For 8 bits that is −128 to +127. The range is lopsided by one because zero takes one of the non-negative patterns. Negating the most negative number gives itself: the two's complement of 1000 0000 is 1000 0000 again, a corner case that has caused real software bugs.

The carry out of the MSB was simply thrown away in that example. In two's complement arithmetic, the carry out does not indicate overflow. A signed overflow happens instead when two numbers with the same sign are added and the result has the opposite sign: two positives giving a negative, or two negatives giving a positive. Adding two numbers with different signs can never overflow. In hardware, signed overflow is detected by comparing the carry into the MSB with the carry out of it: if they differ, the result has overflowed.

Subtraction and sign extension

Because negation is so easy in two's complement, subtraction is done by adding the negation: A − B = A + (B̄ + 1). An adder circuit can subtract by inverting B and setting the carry into the least significant column to 1. Lesson 7 builds exactly this adder-subtractor, which is the heart of every arithmetic logic unit.

When a signed number moves into a wider register, it must be sign-extended: copy the MSB into all the new upper bits. The 4-bit value 1011 (−5) becomes 1111 1011 in 8 bits, still −5. Filling with zeros instead, as you would for an unsigned number, would turn it into 0000 1011, which is +11. Mixing up signed and unsigned extension is one of the most common errors in hardware and software alike.

# Interpret and add 8-bit patterns as unsigned and as two's complement
BITS = 8
def as_signed(x, n=BITS):
    return x - (1 << n) if x & (1 << (n - 1)) else x

def add(a, b, n=BITS):
    mask = (1 << n) - 1
    raw = a + b
    s = raw & mask
    carry = raw >> n                          # unsigned overflow
    sa, sb, ss = as_signed(a), as_signed(b), as_signed(s)
    v = int((sa >= 0) == (sb >= 0) and (ss >= 0) != (sa >= 0))   # signed overflow
    return s, carry, v

for a, b in [(100, 0xD3), (200, 100), (0x70, 0x30), (0x90, 0xA0)]:
    s, c, v = add(a, b)
    print(f"{a:08b} + {b:08b} = {s:08b}  unsigned {a}+{b}={s} C={c}  "
          f"signed {as_signed(a)}+{as_signed(b)}={as_signed(s)} V={v}")

01100100 + 11010011 = 00110111  unsigned 100+211=55 C=1  signed 100+-45=55 V=0
11001000 + 01100100 = 00101100  unsigned 200+100=44 C=1  signed -56+100=44 V=0
01110000 + 00110000 = 10100000  unsigned 112+48=160 C=0  signed 112+48=-96 V=1
10010000 + 10100000 = 00110000  unsigned 144+160=48 C=1  signed -112+-96=48 V=1

The four sums show every case. The first, 100 + (−45), is correct as a signed sum even though it carries out. The second, 200 + 100, overflows as unsigned but not as signed (−56 + 100 = 44 is fine). The third, 112 + 48, is fine unsigned but overflows signed, because two positives gave a negative. The fourth overflows both ways. The hardware performs the same addition every time; only the interpretation, and therefore which flag matters, changes.

Binary-coded decimal

Many products show numbers to people in decimal: meters, clocks, scales, fuel pumps and Cedarline's tachometer display. Converting a binary number to decimal digits takes repeated division, which is expensive in hardware. An alternative is to keep each decimal digit separately in four bits, a code called binary-coded decimal (BCD) or 8421 code after the bit weights. The number 2,795 in BCD is 0010 0111 1001 0101, each nibble one digit. The patterns 1010 to 1111 are unused and illegal.

BCD wastes some bits: four BCD digits use 16 bits to hold 0 to 9,999, while 14 bits of binary would do. In return, each digit can drive a display directly through a decoder (lesson 6), and decimal arithmetic is exact, which is why financial systems and pocket calculators have long used it. Adding two BCD digits uses a binary adder followed by a correction: if the 4-bit sum exceeds 9 or produces a carry, add 6 (0110) to skip the six unused patterns and generate a decimal carry.

Gray code

In ordinary binary counting, several bits can change at once: going from 0111 to 1000 changes all four. If a sensor reads a position as a binary number and the bits do not all change at precisely the same instant, it can briefly report a wildly wrong value, such as 1111 or 0000, during the transition. Gray code fixes this by arranging the patterns so that consecutive values differ in exactly one bit. It is used in rotary and linear position encoders, in counters that cross between clock domains (lesson 11) and in the labeling of Karnaugh maps (lesson 5).

To convert binary to Gray, keep the MSB and make each other Gray bit the exclusive-OR of a binary bit and the bit to its left: gᵢ = bᵢ ⊕ bᵢ₊₁. To convert back, the MSB stays and each binary bit is the exclusive-OR of the Gray bit and the binary bit already found to its left. In a single expression, g = b ⊕ (b ≫ 1).

Characters: ASCII and Unicode

Text is stored by assigning a number to each character. ASCII, the American Standard Code for Information Interchange, uses 7 bits for 128 characters: control codes such as carriage return and line feed (0 to 31), the space, punctuation, digits (0x30 to 0x39), upper-case letters (0x41 to 0x5A) and lower-case letters (0x61 to 0x7A). The layout has handy properties: the digit '7' is 0x37, so subtracting 0x30 gives its value, and upper and lower case differ only in bit 5.

ASCII covers English only. Unicode assigns a code point to every character in every writing system, including accented French letters, Indigenous syllabics, Chinese characters and emoji, more than 150,000 characters in all. The UTF-8 encoding stores each code point in one to four bytes and keeps the 128 ASCII characters as single bytes with the same values, which is why it has become the standard encoding for the web and for most files. A display controller that shows only digits and a few letters may still use plain ASCII internally.

Error detection with parity

Bits can be corrupted by noise on a cable, a radio link or even by a particle striking a memory cell. The simplest protection is a parity bit: an extra bit chosen so that the total number of 1s is even (even parity) or odd (odd parity). The receiver counts the 1s again; if the count has the wrong parity, at least one bit has flipped. Parity detects any single-bit error and any odd number of errors, but it misses an even number of errors and cannot say which bit is wrong.

The parity of a word is the exclusive-OR of all its bits, which is why parity generators and checkers are built from trees of XOR gates. More powerful codes go further. Hamming codes add several parity bits, each covering a different subset of the data, so that a single error can be located and corrected; error-correcting memory in servers uses this idea. Cyclic redundancy checks (CRCs) detect bursts of errors on communication links and in storage. All of them are built from the same XOR operation.

# Gray code and parity, both built from exclusive-OR
def to_gray(b):
    return b ^ (b >> 1)

def from_gray(g):
    b = 0
    while g:
        b ^= g
        g >>= 1
    return b

def even_parity_bit(x):
    p = 0
    while x:
        p ^= x & 1
        x >>= 1
    return p

print("n  binary  gray  back")
for n in range(8):
    g = to_gray(n)
    print(f"{n}  {n:03b}     {g:03b}   {from_gray(g)}")
word = 0b1011001
print(f"data {word:07b} -> parity bit {even_parity_bit(word)} for even parity")

n  binary  gray  back
0  000     000   0
1  001     001   1
2  010     011   2
3  011     010   3
4  100     110   4
5  101     111   5
6  110     101   6
7  111     100   7
data 1011001 -> parity bit 0 for even parity