Number systems and computer codes

(a) $(11011{)}_2$

$$1\times 16+1\times 8+0\times 4+1\times 2+1\times 1=16+8+0+2+1=27$$

(b) $(347{)}_8$

$$3\times 8^2+4\times 8^1+7\times 8^0=3\times 64+4\times 8+7=192+32+7=231$$

(c) $(2\text{AF}{)}_{16}$ — with A $=10$ and F $=15$

$$2\times 256+10\times 16+15\times 1=512+160+15=687$$

(a) Binary — divide by $2$:

$$\begin{array}{rrc}& 93& \\ 2& 46& 1\\ 2& 23& 0\\ 2& 11& 1\\ 2& 5& 1\\ 2& 2& 1\\ 2& 1& 0\\ 2& 0& 1\end{array}$$

Reading upward: $(1011101{)}_2$. Check: $64+16+8+4+1=93$ ✓

(b) Octal — group the binary in threes from the right:

$$1011101\to 001011101\to (135{)}_8$$

Check: $1\times 64+3\times 8+5=64+24+5=93$ ✓

(c) Hexadecimal — group the same bits in fours from the right:

$$1011101\to 01011101\to (5\text{D}{)}_{16}$$

Check: $5\times 16+13=80+13=93$ ✓

Converting once to binary and then regrouping is far quicker than dividing three separate times.

Part 1 — $(0.8125{)}_{10}$ to binary. Multiply by $2$ repeatedly:

$$\begin{array}{rl}0.8125\times 2& =1.625\\ 0.625\times 2& =1.25\\ 0.25\times 2& =0.5\\ 0.5\times 2& =1.0\leftarrow \text{stop}\end{array}$$

Reading the integer parts downward: $(0.1101{)}_2$.

Check: $0.5+0.25+0+0.0625=0.8125$ ✓

Part 2 — $(110.011{)}_2$ to octal. Group in threes outward from the binary point:

$$\underset{6}{\underbrace{110}}.\underset{3}{\underbrace{011}}=(6.3{)}_8$$

Part 3 — the same number to hexadecimal. Group in fours outward from the point, padding at both outer ends:

$$\underset{6}{\underbrace{0110}}.\underset{6}{\underbrace{0110}}=(6.6{)}_{16}$$

Note the padding directions: to the left of the point pad on the far left; to the right of the point pad on the far right. Padding the fraction on the wrong side changes its value.

Check: $(110.011{)}_2=6.375$; $(6.3{)}_8=6+3/8=6.375$ ✓; $(6.6{)}_{16}=6+6/16=6.375$ ✓

(a) Addition $1011+1101$

$$\begin{array}{r}\text{carry: }1111\\ 1011\\ +1101\\ 11000\end{array}$$

Column by column from the right: $1+1=10$ (write $0$, carry $1$); $1+0+1=10$ (write $0$, carry $1$); $0+1+1=10$ (write $0$, carry $1$); $1+1+1=11$ (write $1$, carry $1$); the final carry $1$ is written down.

Result: $(11000{)}_2$. Check: $11+13=24=16+8$ ✓

(b) Subtraction $11010-1011$

$$\begin{array}{r}11010\\ -01011\\ 01111\end{array}$$

From the right: $0-1$ needs a borrow, giving $1$; the next column, now reduced, gives $1$; then $1$; then $1$; then $0$.

Result: $(1111{)}_2$. Check: $26-11=15$ ✓

(c) Multiplication $101\times 110$

$$\begin{array}{r}101\\ \times 110\\ 000(\times 0)\\ 101(\times 1)\\ 101(\times 1)\\ 11110\end{array}$$

Each partial product is either $000$ or a copy of $101$, shifted left one place each time.

Result: $(11110{)}_2$. Check: $5\times 6=30=16+8+4+2$ ✓

1's complement — invert every bit:

$$01101001⟶10010110$$

2's complement — add $1$ to the 1's complement:

$$10010110+1=10010111$$

Shortcut check. Copy bits from the right up to and including the first $1$, then invert the rest. The original ends in $\dots 001$; keeping the final $1$ and inverting everything left of it gives $10010111$ ✓

Why 2's complement is preferred. Three reasons.

1. One zero, not two. In signed magnitude, $00000000$ is $+0$ and $10000000$ is $-0$ — two bit patterns for the same value. Comparisons must then test for both, and one of the $256$ available patterns is wasted. In 2's complement there is exactly one zero, and the 8-bit range is the clean $-128$ to $+127$.

2. Subtraction becomes addition. In 2's complement,

$$A-B=A+(\text{2’s complement of }B)$$

so no subtractor circuit is needed at all — an inverter and the existing adder suffice. In signed magnitude the hardware must compare magnitudes, decide which is larger, subtract the smaller from the larger, and then work out the sign of the answer separately. That is far more circuitry for the same job.

3. Carries need no special handling. Any carry out of the most significant bit is simply discarded and the answer is still correct. The 1's complement scheme instead requires an end-around carry — the carry out must be added back into the least significant bit — which is an extra step and an extra piece of hardware.

Simpler circuitry that is also faster is why every general-purpose processor represents signed integers in 2's complement.

ASCII — American Standard Code for Information Interchange — is a character encoding that assigns a unique number to every letter, digit, punctuation mark and control character. It uses 7 bits, so it defines $2^7=128$ characters, normally stored one per byte. Extended ASCII uses the eighth bit as well, for $256$ characters.

Codes for 'E' and 'e'. The letters are consecutive, so 'E' is the 5th letter:

$$\text{’E’}=65+4=69\text{’e’}=97+4=101$$

The relationship between cases.

$$97-65=32$$

Every lowercase letter is exactly $32$ more than its uppercase counterpart, and this holds for the whole alphabet because both runs are contiguous and in the same order.

Converting case. A program therefore does arithmetic, not a table lookup:

$$\text{uppercase}=\text{lowercase}-32\text{lowercase}=\text{uppercase}+32$$

Since $32=2^5$, the difference is a single bit — bit 5. So the conversion is really one bit operation: clear bit 5 for uppercase, set it for lowercase.

A caution. The program must first check that the character actually is a letter. Blindly subtracting $32$ from a digit or a punctuation mark produces a different, wrong character — subtracting $32$ from '5' ($53$) gives $21$, a control character.

Other useful ASCII facts. Digits '0' to '9' occupy $48$–$57$, so the numeric value of a digit character is its code minus $48$; space is $32$; and carriage return is $13$.

Pure binary treats the number as a single quantity and converts the whole of it. BCD codes each decimal digit separately in 4 bits.

Take $(59{)}_{10}$.

Pure binary:
$$59=32+16+8+2+1=(111011{)}_2\text{— 6 bits}$$

BCD:
$$5\to 0101,9\to 1001$$
$$(59{)}_{10}=(01011001{)}_{\text{BCD}}\text{— 8 bits}$$

The two bit patterns are completely different, and BCD needed two more bits for the same number.

Why BCD is less efficient. Four bits can represent $16$ patterns, but a decimal digit needs only $10$. The six patterns $1010$ to $1111$ are invalid in BCD and simply wasted. The waste grows with the size of the number: representing a 10-digit value takes 40 bits in BCD but only 34 in pure binary. BCD arithmetic is also more complicated, because after adding two BCD digits the hardware must check whether the result exceeded $1001$ and, if so, add $6$ to correct it.

Where BCD is preferred anyway. Whenever the number spends most of its life being displayed or entered as decimal, and comparatively little of it being calculated with.

1. Digital displays, calculators and instruments. Each 4-bit group drives one digit of a seven-segment display directly. In pure binary, showing $59$ on a display would first require dividing by $10$ to extract each digit — a division per digit, per refresh.

2. Exact decimal fractions in financial work. Values such as $0.1$ have no terminating representation in binary, so repeated pure-binary arithmetic on money accumulates rounding error. BCD (and the decimal types built on it) keeps decimal fractions exact, which is why currency is often held in decimal rather than binary floating point.

3. Frequent conversion at the boundary. If a value is read from a keypad and written to a display many times but added only rarely, the cost of conversion dominates the cost of arithmetic — and BCD makes conversion nearly free.

The general principle. Pure binary optimises storage and calculation; BCD optimises conversion to and from decimal, and decimal exactness. Which is more efficient depends entirely on which of those the application does more of.