By the end of this chapter you should be able to:
- Add, subtract and multiply unsigned binary numbers by hand, tracking the carry and borrow through every column.
- Write a signed number in sign-magnitude, 1's complement and 2's complement form, and state the range and the number of zeros in each.
- Perform subtraction by complement addition, using the end-around carry for 1's complement and discarding the carry for 2's complement.
- Detect signed overflow from the carry into and the carry out of the sign position, and explain why a carry out alone does not imply overflow.
- Extend a signed number to a longer word without changing its value, and add BCD digits with the +6 correction.
Chapter 2 fixed how a quantity is written in binary but stopped short of doing anything with it. Arithmetic is where two awkward questions appear at once. The first is mechanical: what are the rules for adding and subtracting bit patterns, and how does a carry propagate? The second is a matter of representation: a register holds nothing but ones and zeros, so where does a minus sign live?
The answer to the second question is the more interesting one, because the representation that the industry settled on — two’s complement — was chosen precisely so that the answer to the first becomes trivial. Subtraction disappears as a separate operation, one adder serves for both, and there is only one pattern for zero. The price is a rule for detecting when a result has silently gone out of range, and that rule catches almost every student once. This chapter derives all of it, then adds the decimal correction that a display-oriented system needs.
1 Binary Addition, Subtraction and Multiplication
Binary arithmetic uses the same column procedure as decimal, with the enormous simplification that each column has only four possible input combinations. For addition:
| \(A\) | \(B\) | Sum | Carry out |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Only the last row generates a carry, and \(1+1 = 10_2\) is not “two” written oddly — it is the digit 0 in this column and a 1 carried into the next, exactly as \(5+5=10\) works in decimal. Including the carry from the column to the right gives three inputs and hence eight cases, which is the truth table of the full adder that Chapter 16 builds from gates.
Add \((01101101)_2 = 109\) and \((01011010)_2 = 90\).
| Row | Bits (MSB first) | Decimal |
|---|---|---|
| Carry into column | 1 1 1 1 0 0 0 0 | — |
| Augend \(A\) | 0 1 1 0 1 1 0 1 | 109 |
| Addend \(B\) | 0 1 0 1 1 0 1 0 | 90 |
| Sum | 1 1 0 0 0 1 1 1 | 199 |
Read the carry row from the right: columns 0 to 2 produce no carry, column 3 has \(1+1\) and starts a carry that then propagates through columns 4, 5 and 6 because each of those has a single 1 plus the incoming carry. That propagation is why a ripple-carry adder is slow: the most significant sum bit cannot settle until a change has walked the whole width of the word.
Subtraction by the direct method needs borrows. The column rules are \(0-0=0\), \(1-0=1\), \(1-1=0\), and \(0-1=1\) with a borrow of 1 from the next column — since \(10_2 - 1 = 1\). Subtracting \((01011100)_2 = 92\) from \((10100011)_2 = 163\) produces borrows into columns 3, 4, 5 and 7 and the difference 01000111, which is 71. The result is correct, but the method has two defects that matter for hardware: it needs a borrow chain that is different circuitry from the carry chain, and it gives no sensible answer when the subtrahend is larger. Section 3 removes both defects.
Multiplication is easier in binary than in any other base, because every partial product is either the multiplicand or zero. There is no multiplication table to remember: test each bit of the multiplier, and if it is 1 write the multiplicand shifted left by that bit position, then add everything.
Multiply \((1101)_2 = 13\) by \((1011)_2 = 11\).
| Multiplier bit | Partial product | Value |
|---|---|---|
| \(b_0 = 1\) | 0000 1101 | 13 |
| \(b_1 = 1\) | 0001 1010 | 26 |
| \(b_2 = 0\) | 0000 0000 | 0 |
| \(b_3 = 1\) | 0110 1000 | 104 |
| Total | 1000 1111 | 143 |
And \(13 \times 11 = 143\). Note that an \(m\)-bit number times an \(n\)-bit number needs up to \(m+n\) bits to hold the product, so a multiplier's output register is always wider than its inputs. Chapter 17 turns this table of partial products directly into an array of AND gates and adders.
2 Three Ways to Represent a Sign
A register has no minus key. If negative numbers are to exist, one of the bits must be spent on the sign, and by universal convention it is the most significant bit: 0 for positive, 1 for negative. What differs between the three schemes is what the remaining bits mean when that sign bit is 1.
- Sign-magnitude. The lower \(n-1\) bits are the magnitude, unchanged. \(-45\) in eight bits is
10101101. Human-readable, and the form used for the mantissa of a floating-point number, but arithmetic needs a comparison of magnitudes before it can decide whether to add or subtract. - 1's complement. Negate by inverting every bit. \(+45\) is
00101101, so \(-45\) is11010010. Equivalently \(-B\) is stored as \((2^n - 1) - B\). - 2's complement. Invert every bit and add 1, so \(-45\) is
11010011. Equivalently \(-B\) is stored as \(2^n - B\). In practice the fastest hand method is to copy the bits from the right up to and including the first 1, then invert every bit above it — which gives the same answer with no addition.
The ranges follow directly from counting patterns, and this is where the three schemes part company.
| Scheme | Range for \(n\) bits | Range for \(n=8\) | Patterns for zero |
|---|---|---|---|
| Sign-magnitude | \(-(2^{n-1}-1)\) to \(+(2^{n-1}-1)\) | −127 to +127 | 2 — 00000000 and 10000000 |
| 1's complement | \(-(2^{n-1}-1)\) to \(+(2^{n-1}-1)\) | −127 to +127 | 2 — 00000000 and 11111111 |
| 2's complement | \(-2^{n-1}\) to \(+(2^{n-1}-1)\) | −128 to +127 | 1 — 00000000 only |
The first two schemes waste a pattern. Eight bits offer 256 codes, but sign-magnitude and 1's complement each spell zero twice, so only 255 distinct values survive. That double-zero problem is not merely inelegant: a comparator that tests a result against zero must then test for two patterns, and a hardware zero flag needs an extra gate. Two's complement has one zero, uses all 256 codes, and gets an extra negative value (−128) for free.
The reason 2's complement has a single zero is worth seeing. Negating 00000000 means inverting to 11111111 and adding 1, which gives 1 00000000; the ninth bit is outside the register and is discarded, leaving 00000000 again. In 1's complement no such addition happens, so the all-ones pattern survives as “minus zero”.
Figure 3.1 also explains the one asymmetry of two's complement. The most negative value, −8 in four bits or −128 in eight, has no positive counterpart. Negating it by the usual recipe returns the same pattern: 10000000 inverts to 01111111, and adding 1 gives 10000000. A processor flags that as an overflow, and any routine that takes an absolute value has to treat it as a special case.
3 Subtraction by Complement Addition
The point of a complement representation is that it converts subtraction into addition. The argument is short. In 2's complement the pattern stored for \(-B\) is \(2^n - B\), so
The unwanted \(2^n\) is a 1 in bit position \(n\) — one place beyond the top of an \(n\)-bit register. It is the carry out, and simply discarding it leaves exactly \(A-B\).
In 1's complement the stored pattern is \((2^n-1)-B\), one less, so the same addition leaves the result one short. The deficit is repaired by taking the carry that fell off the top and adding it back into the least significant position — the end-around carry. That is one extra adder delay on every subtraction, and it is the practical reason 1's complement lost.
In both schemes, a carry out of the most significant position means the answer is positive and already correct. No carry out means the answer is negative and is sitting in the machine in complement form, so it must be complemented again to read its magnitude.
(a) 2's complement, 93 − 45. \(+45\) is 00101101; inverting gives 11010010 and adding 1 gives 11010011 for \(-45\). Then
A carry out appeared, so it is discarded and the answer is 00110000 = 48, positive. And \(93-45=48\).
(b) 1's complement, 93 − 45. The 1's complement of 45 is 11010010, and \(\texttt{01011101} + \texttt{11010010} = \texttt{1}\,\texttt{00101111}\). The result 00101111 is 47, one short. Adding the end-around carry gives 00110000 = 48, the same answer as before but one addition later.
(c) 2's complement, 45 − 93. \(-93\) is 10100011, and \(\texttt{00101101} + \texttt{10100011} = \texttt{11010000}\) with no carry out. No carry means the answer is negative and is already in 2's complement form. To read it, complement again: 11010000 inverts to 00101111 and adding 1 gives 00110000 = 48, so the answer is −48. And \(45-93 = -48\).
(d) 1's complement, 45 − 93. The 1's complement of 93 is 10100010, and \(\texttt{00101101} + \texttt{10100010} = \texttt{11001111}\), again with no carry out. Inverting 11001111 gives 00110000 = 48, so the answer is −48 as before — and here no end-around carry arises, because there was no carry to go round.
The hardware consequence is the one that matters. Because subtraction is addition of a complement, an adder becomes a subtractor if each bit of \(B\) is passed through an XOR gate controlled by a mode line \(M\), with the same \(M\) driving the carry input. With \(M=0\) the XOR gates pass \(B\) unchanged and \(C_0 = 0\), giving \(A+B\); with \(M=1\) they invert \(B\) and \(C_0 = 1\) supplies the “add one”, giving \(A + \bar{B} + 1 = A-B\). Chapter 16 draws that circuit; it is four gates added to an adder you already had.
4 Overflow: When the Answer Will Not Fit
An \(n\)-bit signed register holds values from \(-2^{n-1}\) to \(2^{n-1}-1\) and nothing else. If a sum falls outside that range the adder does not stop; it delivers a pattern that is simply the wrong number, and it is wrong in a characteristic way — the sign flips. Detecting that condition is the job of the overflow flag \(V\).
Two observations narrow the problem. First, adding numbers of opposite sign can never overflow, because the magnitude of the result is no larger than the larger operand, which already fits. Second, adding two numbers of the same sign overflows exactly when the result appears to have the opposite sign. So one test is: if both operands share a sign and the sum does not, there is overflow.
That test is correct but awkward in hardware. The equivalent test that a real adder uses looks only at the carries around the most significant stage:
\(C_{n-1}\) is the carry into the sign position and \(C_n\) the carry out of it. Overflow occurs when exactly one of them is 1. If both are 0 or both are 1, the result is correct.
Why this works can be seen without algebra. The carry into the sign column is the amount the magnitude bits are trying to push into the sign; the carry out is the amount the sign column is passing on. If those two agree, the sign column has behaved consistently with the columns below it. If they disagree, the sign bit has been altered by an amount that the discarded carry does not cancel, and the stored sign no longer means what it should.
In four-bit two's complement the legal range is −8 to +7.
| Sum | As signed | Result | \(C_3\) | \(C_4\) | \(V\) | Verdict |
|---|---|---|---|---|---|---|
0101 + 0110 | (+5) + (+6) = +11 | 1011 = −5 | 1 | 0 | 1 | Overflow — +11 exceeds +7 |
1010 + 1011 | (−6) + (−5) = −11 | 0101 = +5 | 0 | 1 | 1 | Overflow — −11 is below −8 |
1100 + 1110 | (−4) + (−2) = −6 | 1010 = −6 | 1 | 1 | 0 | Correct, despite a carry out |
0011 + 0100 | (+3) + (+4) = +7 | 0111 = +7 | 0 | 0 | 0 | Correct, no carry either way |
Row 3 is the row that settles the argument. There is a carry out of the most significant position, yet the signed answer −6 is perfectly correct. A carry out on its own therefore proves nothing about a signed result — it is the unsigned overflow flag, and the two must never be confused. Row 1 makes the complementary point: the answer is wrong even though no carry left the register at all.
A processor computes both flags on every addition and lets the program choose. Code that treats its data as unsigned branches on the carry flag; code that treats the same bits as signed branches on \(V\). The adder does not know, and does not need to know, which interpretation the programmer had in mind.
5 Sign Extension and Truncation
Numbers frequently have to move between fields of different width: a four-bit sensor reading into an eight-bit accumulator, an eight-bit constant into a sixteen-bit register. Padding an unsigned value with zeros on the left is obviously safe, because leading zeros carry no weight. For a signed value in two's complement, padding with zeros is wrong.
Take \(-5\) in four bits, 1011. Zero-extending to eight bits gives 00001011, which is \(+11\) — not merely a different number but the wrong sign. The correct operation is sign extension: copy the sign bit into every new position. \(-5\) becomes 11111011 in eight bits and 1111111111111011 in sixteen, and \(+5 = \)0101 becomes 00000101.
The justification comes straight from the weights. In an \(n\)-bit two's-complement number the sign bit does not have weight \(+2^{n-1}\) but \(-2^{n-1}\), so
Duplicating the sign bit one place to the left replaces the term \(-b\,2^{\,n-1}\) by \(-b\,2^{\,n} + b\,2^{\,n-1}\), and since \(-2^{n} + 2^{n-1} = -2^{n-1}\) the value is unchanged. Repeat as often as you like: extending by any number of copies of the sign bit is value-preserving, which is why the operation appears as a single instruction on every processor and as a fan-out of one wire in every datapath drawing.
Truncation is the reverse and is not always safe. Discarding leading bits preserves the value only if every bit discarded, and the new sign bit, are all equal to the original sign bit. Reducing 11111011 to four bits gives 1011, still −5, because all the discarded bits were 1s matching the sign. Reducing 00010011 = +19 to four bits gives 0011 = +3, which is nonsense, and a discarded 1 is exactly the warning.
6 BCD Addition and the +6 Correction
Systems that drive a numeric display, such as an energy meter or a weighing scale, often keep their data as binary-coded decimal: each decimal digit stored in its own group of four bits, 0000 to 1001. Chapter 4 treats BCD as a code; here we only need the arithmetic, which does not work the way plain binary does.
The difficulty is a mismatch of moduli. A four-bit adder carries out at 16, but a decimal digit must carry at 10. Six of the sixteen four-bit patterns — 1010 to 1111 — are not valid BCD at all. So a binary sum of two BCD digits goes wrong in two distinct ways: it can land on one of those six illegal patterns, or it can pass 15, produce a carry, and leave a residue that is six too small because the carry was worth 16 when it should have been worth 10.
Both faults have the same size and therefore the same cure. Whenever the four-bit sum exceeds 9, or a carry out of the group occurred, add 0110 to that group and treat the resulting carry as a decimal carry into the next decade.
With group sum bits \(Z_3Z_2Z_1Z_0\) and group carry \(K\), the condition is \(C = K + Z_3Z_2 + Z_3Z_1\). The two product terms cover 12–15 and 10–11 respectively, and \(K\) covers everything from 16 upwards. Chapter 8 shows how that expression is read straight off a K-map of the six illegal patterns.
(a) 25 + 13. Units: \(0101 + 0011 = 1000\) = 8, no carry and not above 9, so no correction. Tens: \(0010 + 0001 = 0011\) = 3. Result 0011 1000 = 38, correct with nothing done.
(b) 47 + 38. Units: \(0111 + 1000 = 01111\) = 15. That is above 9, so add six: \(01111 + 0110 = 10101\), giving a digit of 0101 = 5 and a carry of 1 into the tens. Tens: \(0100 + 0011 + 1 = 1000\) = 8, which needs no correction. Result 1000 0101 = 85, and \(47+38 = 85\).
(c) 68 + 47. Units: \(1000 + 0111 = 01111\) = 15; correct to \(10101\), digit 0101 = 5, carry 1. Tens: \(0110 + 0100 + 1 = 01011\) = 11, which is above 9, so correct again: \(01011 + 0110 = 10001\), digit 0001 = 1 and a carry of 1 into the hundreds. Result 0001 0001 0101 = 115, and \(68+47 = 115\). Note that the carry created by the units correction is what pushed the tens digit over 9, so corrections can cascade.
The cost of BCD is now visible in three forms: extra hardware (a second adder and the detect logic in every decade), extra delay (two adder propagation times per digit rather than one), and the wasted code space noted in Chapter 2. It is paid only where decimal display or exact decimal fractions matter — in instrumentation and in financial arithmetic. Everywhere else the machine computes in plain binary and converts once, at the output, using the converters of Chapter 20.
7 Summary and Key Results
| Item | Rule | Eight-bit instance |
|---|---|---|
| Sign-magnitude | Sign bit plus unchanged magnitude; range \(\pm(2^{n-1}-1)\); two zeros | \(-45 = \)10101101 |
| 1's complement | Invert every bit; range \(\pm(2^{n-1}-1)\); two zeros | \(-45 = \)11010010 |
| 2's complement | Invert and add 1; range \(-2^{n-1}\) to \(2^{n-1}-1\); one zero | \(-45 = \)11010011 |
| Subtraction, 2's comp. | Add the complement and discard the carry out | \(93-45\): carry discarded, answer 48 |
| Subtraction, 1's comp. | Add the complement and add the carry back in (end-around) | \(93-45\): \(47+1 = 48\) |
| Overflow | \(V = C_n \oplus C_{n-1}\) — carry out disagrees with carry into the sign | \(0101+0110\): \(C_3=1, C_4=0, V=1\) |
| Sign extension | Copy the sign bit into every added position | 1011 → 11111011 |
| BCD addition | Add 0110 when a digit sum exceeds 9 or carries out | \(47+38\): \(15+6 = 21\), digit 5 carry 1 |
8 Common Mistakes
They are different flags. In four-bit two's complement, 1100 + 1110 is \((-4)+(-2) = -6\); a carry leaves the register, yet the stored answer 1010 is exactly −6 and nothing is wrong. Conversely 0101 + 0110 produces no carry out at all and the answer is badly wrong. Overflow is \(C_n \oplus C_{n-1}\); carry out alone is only the unsigned result flag.
The two schemes have opposite rules and each is wrong in the other's setting. In 1's complement the final carry must be added back at the least significant end, or every positive result comes out one too small. In 2's complement it must simply be discarded; adding it back gives an answer one too large. Decide which representation you are in before you touch the carry.
Widening 1011 to eight bits as 00001011 turns −5 into +11. Two's-complement values must be sign-extended — the sign bit is copied into every new position — because the most significant bit carries negative weight. The same care applies in reverse: truncating a value is safe only when every bit discarded already matches the sign bit that remains.
9 Chapter Review
1. Write −37 in eight bits in all three signed representations, and state how many distinct values each representation can hold in eight bits.
\(+37\) is
00100101. Sign-magnitude: set the sign bit and keep the magnitude, giving10100101. One's complement: invert every bit, giving11011010. Two's complement: invert and add 1, giving11011011. Sign-magnitude and 1's complement each hold 255 distinct values, because two of the 256 patterns both mean zero; 2's complement holds all 256, covering −128 to +127.2. Evaluate \(57 - 82\) in eight-bit two's complement. State the answer, whether a carry left the register, and whether \(V\) is set.
\(+82\) is
01010010, so \(-82\) is10101110. Adding00111001+10101110gives11100111with no carry out. The operands had opposite signs, so overflow is impossible and \(V = 0\); the absence of a carry out simply signals a negative result. Reading the answer: complementing11100111gives00011001= 25, so the result is −25, and \(57-82 = -25\).3. Add
0110and0101as four-bit signed numbers. Show the carries into and out of the sign position and state whether the result may be used.The bit sum is
1011. Working the columns, bit 3 receives a carry from the lower three columns, so \(C_3 = 1\), while the sign column produces \(0+0+1\) and no carry out, so \(C_4 = 0\). Then \(V = C_4 \oplus C_3 = 1\) and the result must not be used. The arithmetic confirms it: \((+6) + (+5) = +11\), which is outside the four-bit range −8 to +7, and1011would be read as −5.4. Add 68 and 47 in BCD, showing every correction.
Units: \(1000 + 0111 = 01111\) = 15, which exceeds 9, so add
0110to get10101— digit0101= 5 with a carry of 1. Tens: \(0110 + 0100 + 1 = 01011\) = 11, which also exceeds 9, so add0110to get10001— digit0001= 1 with a carry of 1 into the hundreds. The full result is0001 0001 0101= 115, which is \(68+47\). Both decades needed correcting, the second only because the first produced a carry.5. A four-bit two's-complement value
1011is loaded into an eight-bit register. What should the register contain, and what value would a zero-padded load have produced?1011is −5, so the register should contain the sign-extended pattern11111011, which is also −5 in eight bits. A zero-padded load would give00001011= +11 — wrong in magnitude and in sign. Sign extension is value-preserving because duplicating the sign bit replaces the weight \(-2^{n-1}\) with \(-2^{n} + 2^{n-1}\), and those are equal.