By the end of this chapter you should be able to:
- State the weight of any digit position in any base \(r\), and evaluate a number by forming the weighted sum of its digits.
- Convert an integer from decimal to any base by repeated division, and back again by the sum of weights, reading the remainders in the correct order.
- Convert a fraction by repeated multiplication, and explain why a fraction that terminates in decimal need not terminate in binary.
- Convert directly between binary, octal and hexadecimal by grouping bits in threes and fours from the radix point outwards.
- Determine the word length required to cover a given range of values, and the range covered by a given word length.
Chapter 1 argued that a digital circuit should recognise only two voltages. That decision settles how a signal behaves on a wire, but it says nothing yet about how a quantity is written down. A temperature of 173 °C, an address in a memory, the count in a timer — each has to become a pattern of ones and zeros before any gate can act on it, and someone has to fix the rule that connects the two.
That rule is positional notation, and it is exactly the rule you already use for decimal. This chapter states it in a form that works in any base, then applies it four ways: decimal to binary and back, for whole numbers and for fractions, and the shortcuts that make octal and hexadecimal worth having. Every later chapter assumes these conversions are automatic. Chapter 3 adds arithmetic and signs to them, Chapter 4 covers the coded representations that are not plain binary at all, and Chapter 20 builds the circuits that perform some of these conversions in hardware.
1 Positional Notation and Weights
In a positional number system a digit means different things in different places. The two 3s in 3 035 are not equal: the left one counts thousands and the right one counts tens. What makes the system work is that the weight of a position is a power of the base (or radix) \(r\), and the powers run in order.
For a number with \(n\) integer digits and \(m\) fraction digits, written \(d_{n-1}\,d_{n-2}\ldots d_1 d_0 . d_{-1} d_{-2} \ldots d_{-m}\), the value is
Each digit \(d_i\) must satisfy \(0 \le d_i \le r-1\). A base-\(r\) system therefore needs exactly \(r\) distinct symbols, which is why base 16 has to invent six of them.
Two consequences follow immediately and are worth stating separately, because students who know them stop guessing. First, the position immediately left of the radix point always has weight \(r^0 = 1\), whatever the base. Second, weights increase by a factor of \(r\) for each step left and decrease by a factor of \(r\) for each step right; there is no discontinuity at the point. Figure 2.1 shows both for a binary number.
Evaluating that sum is the whole of the conversion from any base to decimal, because you are doing the arithmetic in decimal. So \((3AF)_{16} = 3(256) + 10(16) + 15 = 943_{10}\), and \((736.4)_{8} = 7(64) + 3(8) + 6 + 4/8 = 478.5_{10}\). Note that in hexadecimal the letter A stands for the digit ten and F for fifteen; they are single digits, not multi-digit numbers.
One more consequence is worth stating because it is used constantly in the rest of the course. Multiplying a number by its base shifts every digit one place left, and dividing by the base shifts every digit one place right, because both operations multiply every weight by \(r\) or divide it by \(r\). In binary this means a left shift doubles a value and a right shift halves it, which is why the shift registers of Chapter 26 turn out to be arithmetic units as well as storage.
Because a base is only a choice of weights, the same physical quantity has infinitely many written forms. A subscript is therefore not decoration — \((11)_2 = 3_{10}\) while \((11)_{16} = 17_{10}\), and dropping the subscript in an examination answer is how marks are lost. In hardware documentation the same job is done by prefixes and suffixes such as 0x1F, 1Fh or 16#1F#.
2 Binary, Octal, Hexadecimal and Decimal
Four bases matter in this course, and each is used for a specific reason rather than out of habit.
- Binary, \(r = 2\). Digits 0 and 1, called bits. This is the only base the hardware actually holds, because a two-state device is what a transistor makes well.
- Octal, \(r = 8\). Digits 0 to 7. Three bits per digit. It survives mostly in older minicomputer documentation and in Unix file permissions, and it is convenient when a field happens to be a multiple of three bits wide.
- Hexadecimal, \(r = 16\). Digits 0 to 9 then A, B, C, D, E, F for ten to fifteen. Four bits per digit, so a byte is exactly two hex digits and a 16-bit address is exactly four. This is why every data sheet and every debugger you will meet uses it.
- Decimal, \(r = 10\). The base the specification is written in and the base the display shows. It appears inside a digital system only in coded form — the BCD of Chapter 4 — and never as the natural arithmetic of the machine.
Counting in an unfamiliar base is the fastest way to make it feel ordinary. The rule is the same as in decimal: increment the least significant digit; when it would exceed \(r-1\), set it to zero and carry one into the next position.
| Decimal | Binary | Octal | Hexadecimal |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
| 2 | 10 | 2 | 2 |
| 3 | 11 | 3 | 3 |
| 4 | 100 | 4 | 4 |
| 5 | 101 | 5 | 5 |
| 6 | 110 | 6 | 6 |
| 7 | 111 | 7 | 7 |
| 8 | 1000 | 10 | 8 |
| 9 | 1001 | 11 | 9 |
| 10 | 1010 | 12 | A |
| 11 | 1011 | 13 | B |
| 12 | 1100 | 14 | C |
| 13 | 1101 | 15 | D |
| 14 | 1110 | 16 | E |
| 15 | 1111 | 17 | F |
| 16 | 10000 | 20 | 10 |
Two patterns in that table are worth noticing now because they explain the whole of the grouping method later. Every time the binary column gains a digit — at 2, 4, 8, 16 — the decimal value is a power of two. And the octal column changes its leading digit exactly when the binary column crosses a multiple of three bits, while the hexadecimal column does so at multiples of four. That is not a coincidence: \(8 = 2^3\) and \(16 = 2^4\).
You could build a machine whose arithmetic is decimal, and early calculators did. The cost is that each decimal digit needs four bits, of which only ten of the sixteen patterns are used — a waste of 37.5 % of the code space — and every arithmetic unit needs correction logic of the kind Chapter 3 develops for BCD addition. Binary arithmetic needs no such correction, so machines convert to decimal only at the display.
3 Converting Integers: Repeated Division and Sum of Weights
Going from base \(r\) to decimal is the weighted sum of the previous section. Going the other way needs a method, and the method comes straight out of the same expansion. Write the integer as
and divide both sides by \(r\). Every term except the last contains at least one factor of \(r\), so they all go into the quotient; \(d_0\) is left over. In other words the remainder of \(N \div r\) is the least significant digit, and the quotient is the same number with that digit removed. Repeat on the quotient and the next digit falls out. Stop when the quotient reaches zero.
The first remainder you obtain is the least significant digit and the last is the most significant, so the answer is read upwards from the bottom of the working. Reversing that order is the single commonest error in this chapter.
An alternative for binary, quicker on paper for a number you can size by eye, is to subtract the largest power of two that fits and repeat. For 173: \(173-128 = 45\), \(45-32 = 13\), \(13-8 = 5\), \(5-4 = 1\), \(1-1 = 0\). Ones therefore sit at weights 128, 32, 8, 4 and 1 and zeros everywhere else, giving 10101101 directly, most significant bit first. The two methods are the same arithmetic approached from opposite ends, and each is a check on the other.
The reverse direction — base \(r\) to decimal — needs no algorithm beyond the weighted sum, but for binary there is a shortcut worth having. Because the only digits are 0 and 1, the weighted sum reduces to adding the weights of the positions that hold a 1. For 10101101 the ones sit at weights 128, 32, 8, 4 and 1, and \(128+32+8+4+1 = 173\). No multiplication is involved at all.
Convert the decimal integer 2957 to binary, then read off its octal and hexadecimal forms.
Dividing repeatedly by 2 and recording remainders from the top:
| Division | Quotient | Remainder | Bit |
|---|---|---|---|
| 2957 ÷ 2 | 1478 | 1 | LSB, \(b_0\) |
| 1478 ÷ 2 | 739 | 0 | \(b_1\) |
| 739 ÷ 2 | 369 | 1 | \(b_2\) |
| 369 ÷ 2 | 184 | 1 | \(b_3\) |
| 184 ÷ 2 | 92 | 0 | \(b_4\) |
| 92 ÷ 2 | 46 | 0 | \(b_5\) |
| 46 ÷ 2 | 23 | 0 | \(b_6\) |
| 23 ÷ 2 | 11 | 1 | \(b_7\) |
| 11 ÷ 2 | 5 | 1 | \(b_8\) |
| 5 ÷ 2 | 2 | 1 | \(b_9\) |
| 2 ÷ 2 | 1 | 0 | \(b_{10}\) |
| 1 ÷ 2 | 0 | 1 | MSB, \(b_{11}\) |
Reading the remainder column upwards, \((2957)_{10} = (1011\,1000\,1101)_2\). Check it by the sum of weights: the ones lie at 2048, 512, 256, 128, 8, 4 and 1, and \(2048+512+256+128+8+4+1 = 2957\). Grouping the same bits in threes gives \((5615)_8\) and in fours gives \((\text{B8D})_{16}\); Section 5 explains why that works.
Always check an integer conversion by the weighted sum. It costs a few seconds and catches both a dropped remainder and a reversed reading order.
4 Converting Fractions: Repeated Multiplication
A fraction cannot be converted by division, because it has no remainders to give up. It is converted by the mirror-image argument. Write the fraction as
and multiply both sides by \(r\). The first term becomes \(d_{-1}\), a whole number, and every other term still carries at least one negative power of \(r\) and so remains a fraction. Multiplying by the base therefore pushes one digit across the radix point, where it can be read off. Discard that integer part and repeat with the fraction that is left.
Here the order is the opposite of the integer case: the first digit produced is the one immediately after the radix point. Read downwards. The process ends when the remaining fraction becomes exactly zero — and it may never do so.
(a) Convert 0.6875 to binary.
| Step | Product | Digit taken | Fraction carried on |
|---|---|---|---|
| 0.6875 × 2 | 1.375 | 1 | 0.375 |
| 0.375 × 2 | 0.75 | 0 | 0.75 |
| 0.75 × 2 | 1.5 | 1 | 0.5 |
| 0.5 × 2 | 1.0 | 1 | 0 — stop |
Reading downwards, \((0.6875)_{10} = (0.1011)_2\). Verify with weights: \(\tfrac12 + \tfrac18 + \tfrac{1}{16} = 0.5 + 0.125 + 0.0625 = 0.6875\).
(b) Convert 0.7 to binary. The same procedure gives digits 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, … and the carried fraction runs \(0.4,\ 0.8,\ 0.6,\ 0.2,\ 0.4,\ 0.8,\ \ldots\) — the value 0.4 has returned, so the block 0110 repeats for ever:
Truncating to eight bits gives 0.10110011, which is 0.69921875 — an error of 0.00078125, about 0.11 %.
Part (b) is not a curiosity; it is the normal case. A fraction terminates in base \(r\) only if, in lowest terms, its denominator divides some power of \(r\). Since \(2^k\) has no factor of 5, a decimal fraction terminates in binary only when its denominator is a power of two. \(0.5\), \(0.25\) and \(0.6875 = 11/16\) are fine; \(0.1\), \(0.2\), \(0.3\) and \(0.7\) all recur. The everyday consequence is that a controller which accumulates a 0.1 s tick in binary drifts, while one that accumulates a 0.125 s tick does not.
Because the expansion may not terminate, converting a fraction always involves a decision about how many digits to keep, and that decision fixes the resolution. With \(m\) fraction bits the finest distinguishable step is \(2^{-m}\): four bits resolve to \(0.0625\), eight bits to \(0.00390625\), ten bits to about one part in a thousand. Chapter 29 calls the same quantity the quantisation step of a converter, and the arithmetic there is exactly the arithmetic here.
5 Grouping in Threes and Fours, and a Mixed Number Both Ways
Nothing so far has treated octal and hexadecimal as anything special, and by the general method they are not: you could convert to hexadecimal by dividing repeatedly by 16. But because \(8 = 2^3\) and \(16 = 2^4\), a far shorter route exists, and it is the reason those two bases are used at all.
Take a group of three adjacent bits sitting at weights \(2^{k+2}, 2^{k+1}, 2^{k}\) where \(k\) is a multiple of three. Their combined contribution is \(2^{k}\,(4b_2 + 2b_1 + b_0)\), and the bracket runs from 0 to 7 — precisely one octal digit — while \(2^k = 8^{k/3}\) is precisely the corresponding octal weight. So a group of three bits is an octal digit, with no arithmetic in between. The same argument with four bits gives a bracket running from 0 to 15 and a weight \(2^k = 16^{k/4}\): a group of four bits is a hexadecimal digit.
The argument only holds if the groups are aligned so that the lowest group starts at weight \(2^0\). That is why grouping always begins at the radix point and works outwards in both directions, padding with zeros at the far ends: leading zeros on the left of the integer part and trailing zeros on the right of the fraction. Both kinds of padding are harmless because they add zero weight. Grouping from the left-hand end of the string instead is the classic way to get a plausible but wrong answer.
Converting between octal and hexadecimal has no direct shortcut, because 8 is not a power of 16. The practical route is to expand each octal digit into three bits, regroup the same bit string in fours, and read off the hexadecimal — or the reverse. Binary is the pivot in both directions.
Forward. The integer part was converted in Example 2.1 and the fraction in Example 2.2(a), so
Group in fours from the point: 1011 1000 1101 . 1011, giving digits 11, 8, 13 and 11, that is \((\text{B8D.B})_{16}\). Group the same string in threes, padding the fraction with two zeros to complete the last group: 101 110 001 101 . 101 100, giving \((5615.54)_8\).
Backward. Start from \((\text{B8D.B})_{16}\) and expand every digit into four bits — B = 1011, 8 = 1000, D = 1101 — to recover 101110001101.1011. Now evaluate the weighted sum. The integer ones lie at 2048, 512, 256, 128, 8, 4 and 1:
and the fraction ones at \(2^{-1}\), \(2^{-3}\) and \(2^{-4}\):
The total is 2957.6875, the number we started from. As a second, independent check, evaluate the hexadecimal form directly: \(11(256) + 8(16) + 13 + 11/16 = 2816 + 128 + 13 + 0.6875 = 2957.6875\).
Notice how much shorter the hexadecimal form is. Twelve bits and a four-bit fraction became four characters. That compression, with no loss and no arithmetic, is the entire justification for hexadecimal: it is a way of writing binary that a human can read aloud and copy without error, not a different number system in any meaningful sense.
6 Range, Resolution and Word Length
A register, a bus or a memory location holds a fixed number of bits, and that number decides what can be represented. With \(n\) bits there are \(2^n\) distinct patterns, so an unsigned integer field of \(n\) bits covers
and no value outside that range exists as far as the hardware is concerned. Eight bits reach 255, twelve bits 4095, sixteen bits 65 535. Chapter 3 spends part of a field on a sign and roughly halves the positive reach.
Turned round, the design question is usually the other one: how many bits do I need? To represent every integer from 0 to \(N_{\max}\) you need the smallest \(n\) satisfying \(2^n \ge N_{\max}+1\), that is \(n = \lceil \log_2 (N_{\max}+1) \rceil\). In practice you count powers of two rather than take logarithms.
(a) A counter must count from 0 to 5000. Since \(2^{12} = 4096\) is too small and \(2^{13} = 8192\) is enough, 13 bits are needed. The counter can then reach 8191, so 3191 of its states are unused and the design must decide what happens if the count ever enters them — a point Chapter 25 returns to as self-starting behaviour.
(b) A memory of 4096 locations needs \(\log_2 4096 = 12\) address lines, because 12 bits address exactly \(2^{12} = 4096\) locations, 0 to 4095. Written in hexadecimal that range is 000 to FFF — three digits, one per four address lines, which is precisely why memory maps are always drawn in hex. Chapter 27 uses this arithmetic for address decoding.
The same counting argument answers a question that recurs throughout the course: how efficiently is a code using its patterns? Twelve bits of straight binary reach 4095. Twelve bits of BCD, four per decimal digit, reach only 999, because six of every sixteen patterns are never used. That loss is the price of easy decimal display, and Chapter 4 sets out when it is worth paying.
Finally, a word about vocabulary you will meet on data sheets. The least significant bit (LSB) is the one with weight \(2^0\) and the most significant bit (MSB) the one with the largest weight. A group of four bits is a nibble and eight bits a byte, so one nibble is one hexadecimal digit. Whether the MSB is drawn on the left, and whether the low byte of a multi-byte value is stored at the lower address, are conventions that have to be agreed between two devices before they can exchange anything at all.
7 Summary and Key Results
| Conversion | Procedure | Worked instance |
|---|---|---|
| Any base → decimal | Weighted sum \(\sum d_i r^{\,i}\); for binary, add the weights where a 1 appears | \((10101101)_2 = 128+32+8+4+1 = 173\) |
| Decimal integer → base \(r\) | Divide repeatedly by \(r\); read remainders upwards (LSB first) | \((2957)_{10} = (101110001101)_2\) |
| Decimal fraction → base \(r\) | Multiply repeatedly by \(r\); read integer parts downwards (MSB first) | \((0.6875)_{10} = (0.1011)_2\) |
| Binary ↔ octal | Group in threes from the radix point outwards, padding with zeros | \((101110001101.1011)_2 = (5615.54)_8\) |
| Binary ↔ hexadecimal | Group in fours from the radix point outwards, padding with zeros | \((101110001101.1011)_2 = (\text{B8D.B})_{16}\) |
| Octal ↔ hexadecimal | Expand to bits, regroup, read back — binary is the pivot | \((5615)_8 = (\text{B8D})_{16}\) |
| Word length | \(n\) bits cover \(0\) to \(2^n-1\); need \(n=\lceil\log_2(N_{\max}+1)\rceil\) | 0 to 5000 needs 13 bits |
8 Common Mistakes
Repeated division delivers the least significant digit first, so the answer is built from the bottom of the working upwards. Reading 173 as 10110101 instead of 10101101 gives 181, a number that looks entirely plausible and is simply wrong. Check every integer conversion by the sum of weights before writing it down. The fraction procedure runs the other way — downwards — which is exactly why the two are so easy to confuse.
Groups of three or four must be formed outwards from the radix point, not from whichever end of the string is nearest. Reading 101110001101 in fours from the left gives 1011, 1000, 1101 only because the string happens to be twelve bits long; for an eleven-bit string the same habit shifts every group by one place and every digit comes out wrong. Pad with leading zeros on the integer side and trailing zeros on the fraction side, then group.
Only fractions whose denominator is a power of two terminate in binary, so 0.5, 0.25 and 0.6875 are exact while 0.1, 0.2 and 0.7 recur for ever. Stopping the multiplication after a few digits is not an exact conversion but a truncation, and the residual error must be quoted or at least acknowledged. Writing \((0.1)_{10} = (0.0001100)_2\) with an equals sign, rather than an approximation sign, is the mistake.
9 Chapter Review
1. Convert \((453)_{10}\) to binary, octal and hexadecimal, and verify the binary result.
Repeated division by 2 gives remainders 1, 0, 1, 0, 0, 0, 1, 1, 1 from the quotients 226, 113, 56, 28, 14, 7, 3, 1, 0. Read upwards: \((453)_{10} = (111000101)_2\). Check by weights: the ones lie at 256, 128, 64, 4 and 1, and \(256+128+64+4+1 = 453\). Group in threes from the point, padding to
111 000 101, giving \((705)_8\); group in fours, padding to0001 1100 0101, giving \((1\text{C}5)_{16}\).2. Convert \((10110111.101)_2\) to decimal, octal and hexadecimal.
Integer weights where a 1 appears: \(128+32+16+4+2+1 = 183\). Fraction: \(2^{-1} + 2^{-3} = 0.5 + 0.125 = 0.625\). So the value is \(183.625_{10}\). For octal, group in threes from the point with a leading zero:
010 110 111 . 101= \((267.5)_8\). For hexadecimal, group in fours with a trailing zero in the fraction:1011 0111 . 1010= \((\text{B7.A})_{16}\).3. Convert 0.3 to binary, keeping eight fraction bits. What is the truncation error?
Multiplying repeatedly by 2 gives integer parts 0, 1, 0, 0, 1, 1, 0, 0 and then the carried fraction 0.8 recurs, so \((0.3)_{10} = (0.01\overline{0011})_2\). Truncated to eight bits the value is
0.01001100, which equals \(2^{-2} + 2^{-5} + 2^{-6} = 19/64 = 0.296875\). The error is \(0.3 - 0.296875 = 0.003125\), about 1.04 % of the intended value, and it is a one-sided error because truncation can only lose weight, never add it.4. A tachometer must display any speed from 0 to 20 000 r/min as an integer. How many bits does the register need, and what is the largest value a 14-bit register could hold?
You need \(2^n \ge 20\,001\). Since \(2^{14} = 16\,384\) is too small and \(2^{15} = 32\,768\) is sufficient, the register needs 15 bits. A 14-bit register holds \(2^{14}-1 = 16\,383\) at most, which is short of the requirement by 3617 counts — the reading would wrap round rather than saturate, and a speed of 20 000 would be displayed as 3616.
5. Convert \((7\text{A}5.\text{C})_{16}\) to octal without passing through decimal.
Expand each hexadecimal digit into four bits: 7 =
0111, A =1010, 5 =0101, C =1100, giving011110100101.1100. Now regroup the same bits in threes from the radix point, padding the fraction with two zeros:011 110 100 101 . 110 000. Reading the groups gives \((3645.6)_8\). As a check, both forms evaluate to 1957.75 in decimal.