Corrected exercises: binary arithmetic and machine numbers (201-N11)

Work right to left. Column of weight 1: $0+1=1$, no carry. Weight 2: $1+1=10_2$, write $0$ and carry $1$. Weight 4: $1+0+1=10_2$, write $0$, carry $1$. Weight 8: $0+1+1=10_2$, write $0$, carry $1$. Weight 16: $1+0+1=10_2$, write $0$, carry $1$. Weight 32: $1+1+1=11_2$, write $1$, carry $1$. Weight 64: $0+0+1=1$, no carry. Weight 128: $1+0+0=1$. Result $11100001_2$. Decimal check: $10110110_2 = 128+32+16+4+2 = 182$ and $00101011_2 = 32+8+2+1 = 43$, so the sum must be $225$; and $11100001_2 = 128+64+32+1 = 225$. Two independent routes agree, which is the whole point of writing the weights above the columns.

$1111_2 = 15$ and adding $1$ gives $16 = 10000_2$, which needs five bits. On a 4-bit register the stored result is $0000$ and the fifth bit leaves the adder as a carry out. The value $16$ is not lost because the adder failed; it is lost because nobody kept the carry. This is the difference between the arithmetic, which is always right, and the storage, which has a width.

$1011_2 = 11$, $1101_2 = 13$, $111_2 = 7$, so the sum is $31 = 11111_2$. Verify: weight 1 column has three $1$s, that is $11_2$, so write $1$ and carry $1$; weight 2 has $1+0+1$ plus the carry, that is $11_2$ again. With three operands a column can produce a carry of $2$, not just $1$, so a carry may have to jump two columns. That is exactly why hardware adds numbers two at a time rather than in one wide gulp.

$10011_2 + 1101_2$. Align on the right: $10011_2$ has weights $16+2+1$ and $1101_2$ has $8+4+1$. Adding the weights gives $16+8+4+2+1+1 = 32$, and $32 = 100000_2$. The posed addition gives the same: the two $1$s of weight 1 make a carry into weight 2, which then meets $1+0$, carries again, and the carry ripples all the way to weight 32. Checking by weights is the faster control here because the answer is a single power of two, which is instantly recognisable.

The longest chain is $11111111_2 + 00000001_2$: the carry born in the rightmost column is regenerated by every column it enters and only stops after leaving the leftmost one. The sum is $256 = 100000000_2$. In a ripple-carry adder each column has to wait for the previous carry, so the delay of the whole circuit is set by this worst case and grows with the word width. That is the reason processors use carry-lookahead adders, which compute the carries in parallel from the operand bits instead of passing them along.

$11010_2 - 1011_2$, aligned on the right. Weight 1: $0-1$ is impossible, borrow from weight 2. That column holds $1$, so it becomes $0$ and weight 1 becomes $10_2 = 2$; then $2-1 = 1$. Weight 2: now $0-1$, borrow again from weight 4, which holds $0$, so the borrow has to come from weight 8. Carrying the borrow through gives $1$ at weight 2 and $1$ at weight 4. Weight 8: $0-1$ after the borrow, take from weight 16, giving $1$. Result $1111_2$. Decimal check: $11010_2 = 26$, $1011_2 = 11$, and $26-11 = 15 = 1111_2$. Borrowing across a run of zeros is where mistakes happen, and the decimal check is what catches them.

Two's complement of $00001011_2$ on 8 bits: invert every bit to get $11110100_2$, then add $1$ to get $11110101_2$. As an unsigned pattern that is $245$, and $245 = 256-11$, which is the definition of the complement on 8 bits. Now add: $00011010_2 + 11110101_2 = 26 + 245 = 271$. In binary $271 = 100001111_2$, nine bits. Keep the low eight: $00001111_2 = 15$. Same answer as a), obtained without a single borrow.

$1000000_2 = 64$ and $1_2 = 1$, so the answer is $63 = 111111_2$. The borrow starts at weight 1 and finds a zero in every column until weight 64, so it crosses six columns and turns each zero it passes into a $1$. This is the mirror image of exercise 1e): subtracting $1$ from a power of two is the worst case for borrows, just as adding $1$ to all ones is the worst case for carries.

Two's complement of $00001101_2$ (that is $13$): invert to $11110010_2$, add $1$ to get $11110011_2 = 243 = 256-13$. Add: $00000101_2 + 11110011_2 = 5+243 = 248 = 11111000_2$. Read as signed 8-bit, the leading bit is $1$, so the value is $248-256 = -8$. And indeed $5-13 = -8$. Notice that the adder did nothing special: it added two unsigned patterns. The minus sign only appeared when we chose to read the result as signed.

The complement of $x$ on $n$ bits is $2^{n}-x$, so adding it adds an extra $2^{n}$ that lands entirely in bit $n$, outside the word. Dropping that bit subtracts the $2^{n}$ back out, which is why the low eight bits are the correct difference. The case where it must not be dropped is unsigned addition: there the ninth bit is a genuine carry out saying the true sum did not fit, and ignoring it turns $300$ into $44$. Same bit, opposite meaning, decided by the type you declared and not by the hardware.

$1011_2 \times 101_2$. The multiplier $101_2$ has ones at weights $1$ and $4$, so there are two partial products: $1011_2$ itself, and $1011_2$ shifted two places, that is $101100_2$. Add them: $1011_2 + 101100_2 = 11 + 44 = 55 = 110111_2$. Decimal check: $1011_2 = 11$, $101_2 = 5$, $11 \times 5 = 55$, and $110111_2 = 32+16+4+2+1 = 55$. There is no multiplication table to remember in binary, only shifting and adding.

$100_2 = 4 = 2^{2}$, so multiplying by it shifts the pattern two places to the left and appends two zeros: $110110_2$ becomes $11011000_2$. The justification is positional: shifting left by $k$ multiplies every weight by $2^{k}$, hence the whole number by $2^{k}$. Check: $110110_2 = 32+16+4+2 = 54$ and $11011000_2 = 128+64+16+8 = 216 = 54 \times 4$. This is why a compiler replaces a multiplication by a constant power of two with a shift.

$1000_2 = 8 = 2^{3}$, so shift right by three: $10110100_2$ becomes $10110_2$, and the three bits pushed off the right end are $100_2$. Quotient $10110_2 = 22$, remainder $100_2 = 4$. Check: $10110100_2 = 180$ and $180 = 8 \times 22 + 4$. The remainder is not computed, it is simply the bits that fell off, which is the fastest possible modulo by a power of two: mask with $2^{k}-1$.

A logical shift feeds zeros in on the left: $11110000_2$ becomes $00111100_2 = 60$. An arithmetic shift replicates the sign bit: it becomes $11111100_2$, which read as signed is $252-256 = -4$. If the pattern is signed, $11110000_2$ is $240-256 = -16$, and $-16/4 = -4$: the arithmetic shift is the division, the logical one turns a negative number into a large positive one. Choosing the wrong shift on a signed value does not produce a small rounding error, it produces a number of the wrong sign and roughly the right magnitude, which is exactly the kind of bug that survives testing.

$m+n$ bits are enough, and sometimes necessary. The largest operands are $2^{m}-1$ and $2^{n}-1$, and their product is $2^{m+n} - 2^{m} - 2^{n} + 1$, which is strictly less than $2^{m+n}$, so $m+n$ bits always suffice. They can also be needed: $2^{m-1} \times 2^{n-1} = 2^{m+n-2}$ already requires $m+n-1$ bits, and the largest product above requires $m+n$. This is why hardware multipliers write into a double-width register, and why in C the product of two $32$-bit integers overflows unless one operand is widened first.

Start from $+27 = 16+8+2+1 = 00011011_2$. Invert every bit: $11100100_2$. Add one: $11100101_2$. Check by the definition: as an unsigned pattern, $11100101_2 = 128+64+32+4+1 = 229$, and $229 = 256-27$, which is what $-27$ must be on the 8-bit wheel. A second check costs nothing: adding $00011011_2$ and $11100101_2$ gives $256$, that is $00000000_2$ with a carry out, and a number plus its opposite is zero.

Signed: the leading bit is $1$, so the pattern sits in the negative half. Its unsigned value is $128+32+16+2+1 = 179$, therefore the signed value is $179-256 = -77$. Unsigned: the very same bits are simply $179$. Nothing in memory distinguishes the two readings; the type declared in the program does. Reading a signed byte as unsigned is how a temperature of $-77$ becomes a reading of $179$.

$-128$ is $10000000_2$. Invert: $01111111_2$. Add one: $10000000_2$, the pattern we started from. So on 8 bits, $-128$ is its own opposite: $+128$ does not exist in the range. This is not a defect of the rule, it is the wheel closing on itself, and it is a real source of bugs. In C, taking the absolute value of the most negative integer returns that same negative number, and a routine that assumes $|x| \ge 0$ can loop forever on it.

On $n$ bits the range is $-2^{n-1}$ to $2^{n-1}-1$. Count the patterns: there are $2^{n}$ of them, split into $2^{n-1}$ with a leading $1$, all negative, and $2^{n-1}$ with a leading $0$, covering zero and the positives. Zero uses one pattern from the second half, so only $2^{n-1}-1$ remain for the positive values while the negatives keep all $2^{n-1}$. The asymmetry is the price of having a single representation of zero, and that single zero is what makes ordinary addition work without sign tests.

$-27$ on 16 bits is $1111111111100101_2$, that is $\text{FFE5}_{16}$. Check: as unsigned that pattern is $65509 = 65536-27$. The rule is sign extension: to widen a signed number, copy the sign bit into every new position on the left, not zeros. Filling with zeros instead is the classic widening bug, because $11100101_2$ becomes $0000000011100101_2 = 229$, so a small negative number turns into a mid-sized positive one, silently and with no error raised.

$200 = 11001000_2$ and $100 = 01100100_2$. The true sum is $300 = 100101100_2$, nine bits, so the stored byte is $00101100_2 = 44$ and the carry out is $1$. Unsigned reading: wrong, and the carry out says so, since $300$ does not fit in $[0, 255]$. Signed reading: $11001000_2$ is $200-256 = -56$ and $01100100_2$ is $+100$, so the intended sum is $-56+100 = 44$, and $44$ is exactly what is stored. Correct. One addition, a carry out, and a perfectly right answer.

$100+50 = 150 = 10010110_2$, eight bits, so there is no carry out. Unsigned reading: correct, $150$ is stored. Signed reading: both operands are positive, but the stored pattern has a leading $1$ and reads as $150-256 = -106$. Wrong, and no carry out warned about it. Cases a) and b) are the proof that the carry out is not a general error flag: here it is the mirror image of a), right where a) was wrong and silent where a) shouted.

Signed overflow happens exactly when the two operands have the same sign and the result has the opposite sign. Equivalently, in hardware, when the carry into the sign column differs from the carry out of it. Two operands of opposite signs cannot overflow because the true sum lies strictly between them, and both of them are already inside the representable range, so the sum is inside it too. That is why an overflow check only ever needs to look at three bits, not at the magnitudes.

$-100$ is $156 = 10011100_2$ and $-50$ is $206 = 11001110_2$. The adder computes $156+206 = 362$, so the carry out is $1$ and the stored byte is $362-256 = 106 = 01101010_2$. Read as signed, that is $+106$, while the true answer is $-150$. Both operands were negative and the result came out positive, so this is overflow by the rule in c). The true value $-150$ is below $-128$ and simply has no 8-bit pattern. The carry out here is meaningless: for a signed reading it is a by-product, not a diagnostic.

No carry, no overflow: $30+40 = 70$, which fits both readings. Carry without overflow: $200+100$ from a), which is $-56+100$ read as signed. Overflow without carry: $100+50$ from b). Both at once: $-100+(-50)$ from d), or more starkly $-128 + (-128)$, where $10000000_2 + 10000000_2$ gives a carry out and stores $00000000_2$, so the machine reports that two of the most negative numbers add up to zero. Four combinations, one adder, and the flag you must read depends entirely on the type you declared.

$\text{4}_{16} = 0100_2$ and $\text{9}_{16} = 1001_2$, so $\text{49}_{16} = 01001001_2 = 73$. The bits set are those of weight $1$, $8$ and $64$, that is bits $0$, $3$ and $6$. So READY is on, BUSY is on, ERROR is off, POWER is off, and reserved bit $6$ is on, which is precisely why every operation below must be surgical.

To force a bit to $1$ without touching the others, OR with a mask that has a $1$ in that position only: $R \ \text{OR}\ \text{02}_{16}$. Bitwise OR leaves a bit unchanged when the mask bit is $0$, since $x + 0$ in the OR sense is $x$. Result: $73\ \text{OR}\ 2 = 75 = \text{4B}_{16} = 01001011_2$. Reserved bit $6$ is still on, as required.

To force a bit to $0$, AND with the complement of its mask: BUSY is $\text{08}_{16}$, whose complement on 8 bits is $\text{F7}_{16} = 11110111_2$. So $R \ \text{AND}\ \text{F7}_{16} = 73\ \text{AND}\ 247 = 65 = \text{41}_{16} = 01000001_2$. Every position where the mask has a $1$ is preserved, and only bit $3$ is cleared. Writing the mask as $\text{F7}$ rather than $247$ is not a style choice: in hexadecimal you can see the single zero, in decimal you cannot.

To flip a bit, XOR with its mask: $R\ \text{XOR}\ \text{80}_{16} = 73\ \text{XOR}\ 128 = 201 = \text{C9}_{16} = 11001001_2$. XOR leaves a bit unchanged against a $0$ and inverts it against a $1$, which makes it the only one of the three operations that is its own inverse: applying it twice restores the register. Summary worth memorising: OR sets, AND with a complement clears, XOR toggles.

Mask both flags at once and compare with the mask itself: $(R\ \text{AND}\ \text{09}_{16}) = \text{09}_{16}$. Here $73\ \text{AND}\ 9 = 9$, so the test is true. The obvious shorter test, $(R\ \text{AND}\ \text{09}_{16}) \ne 0$, is a different question: it is true as soon as at least one of the two flags is on. On a register where READY is on and BUSY is off it returns true, and the driver starts a transfer on a device that is not idle. Masking tells you which bits survive; only the comparison tells you how many of them did.

Either shift the masked value down, $(R\ \text{AND}\ \text{08}_{16})$ shifted right by $3$, which gives $8/8 = 1$; or compare, writing the test as $(R\ \text{AND}\ \text{08}_{16}) \ne 0$, which yields a boolean directly. The comparison is what a compiler prefers, because it maps to a single flag test in the condition register with no shift at all, and because it keeps working unchanged if the flag later moves to another bit position. The shift version has to be edited every time the hardware map changes.

$0.6875 \times 2 = 1.375$, digit $1$, keep $0.375$. $0.375 \times 2 = 0.75$, digit $0$. $0.75 \times 2 = 1.5$, digit $1$, keep $0.5$. $0.5 \times 2 = 1.0$, digit $1$, remainder zero, stop. Reading the digits in the order produced gives $0.1011_2$. Check by weights: $0.5 + 0.125 + 0.0625 = 0.6875$. The reading order matters and it is the reverse of the integer case: here top to bottom, there bottom to top. Mixing the two is the single most common error in this chapter and it produces a plausible looking wrong answer.

$0.1 \times 2 = 0.2$ gives $0$; $0.4$ gives $0$; $0.8$ gives $0$; $1.6$ gives $1$, keep $0.6$; $1.2$ gives $1$, keep $0.2$; and now $0.2$ has already occurred, so the block $0011$ repeats for ever: $0.1 = 0.0\overline{0011}_2$. The process does not stop, and it will not stop with more bits, more memory or a better processor. Every machine that stores $0.1$ stores something else, slightly larger or smaller depending on where it cuts.

A fraction has a finite binary expansion if and only if, written in lowest terms, its denominator is a power of $2$. A finite expansion with $k$ fractional bits is a number of the form $m/2^{k}$, so the reduced denominator can only be a power of two; conversely any $m/2^{k}$ is written directly with $k$ bits. Thus $0.5$, $0.25$ and $0.6875 = 11/16$ are exact, while $0.1 = 1/10$ and $0.2 = 1/5$ are not, because $10$ and $5$ carry a factor $5$ that no power of two can cancel.

Q4.4 means the stored 8-bit integer represents the value divided by $2^{4} = 16$. For $5.75$: $5.75 \times 16 = 92$, and $92 = 01011100_2$, so the integer part is $0101$ and the fraction $1100$, that is $0101\,1100_2 = \text{5C}_{16}$. Resolution: one unit of the stored integer is $1/16 = 0.0625$, so nothing finer can be expressed. Range: from $0$ to $255/16 = 15.9375$. Fixed point is just integer arithmetic with an agreed scale factor, which is why it is used on processors without a floating point unit.

$0.1$ is not a multiple of $1/16$: $0.1 \times 16 = 1.6$, which rounds to $2$, so the stored value is $2/16 = 0.125$. Every addition therefore adds $0.125$, not $0.1$. After ten additions the counter holds $1.25$ instead of $1.0$: an absolute error of $0.25$ and a relative error of $25\%$. The error did not creep in, it was decided at the first rounding and then multiplied by ten. This is the argument for choosing a scale that matches the data: in a format scaled by $100$ instead of $16$, $0.1$ is exact.

It should store integer cents, not dollars. Cents are exact integers in any base, additions of integers never round, and the total is converted to dollars once, at the moment of display. Storing dollars as binary fractions means that neither $0.10$ nor $0.01$ is exact, so each of the thousands of additions can be off by a fraction of a cent and the accumulated drift eventually shows up as a total that does not match the sum of the printed lines. Financial software stores integers or decimal types for this reason alone.

FALSE on two counts. First, the quotient is an integer: $7 = 111_2$ shifted right gives $11_2 = 3$, not $3.5$, and the discarded bit is the remainder. Second, on a negative number the answer depends on which shift is used: $-7$ on 8 bits is $11111001_2$, and an arithmetic shift gives $11111100_2 = -4$, while a logical shift gives $01111100_2 = 124$. Corrected statement: an arithmetic right shift by $k$ divides a signed number by $2^{k}$ and rounds towards minus infinity, while a logical right shift divides an unsigned number by $2^{k}$; the two agree only on non-negative values. Note in passing that $-7$ shifted gives $-4$ whereas division in C gives $-3$, so a compiler cannot blindly replace a division by a shift.

FALSE. The range is $-128$ to $+127$. Counting settles it: $256$ patterns, $128$ with a leading $1$ for the negatives and $128$ with a leading $0$ shared between zero and the positives, so the positives get only $127$ of them. Corrected statement: on $n$ bits, two's complement covers $[-2^{n-1},\ 2^{n-1}-1]$, an asymmetric interval, because zero has a single representation and it sits on the positive side.

FALSE. The carry out only condemns an unsigned reading. Counterexample: $200+100$ on 8 bits produces a carry out and stores $44$; read as signed those operands are $-56$ and $+100$, and $44$ is the exact answer. Conversely $100+50$ produces no carry out at all and yet is wrong when read as signed, since it stores $-106$. Corrected statement: for an unsigned reading the error flag is the carry out; for a signed reading it is overflow, which is when the operands share a sign and the result does not.

FALSE. A single precision float spends $1$ bit on the sign and $8$ on the exponent, leaving $23$ stored significand bits plus one implied, so only $24$ bits of precision. Every integer up to $2^{24} = 16\,777\,216$ is exact, but $16\,777\,217$ is not: it rounds to $16\,777\,216$. A 32-bit integer, by contrast, is exact up to $2^{31}-1$. Corrected statement: a float trades precision for range, so it reaches far larger magnitudes than a 32-bit integer while representing far fewer integers exactly.

FALSE. That description is sign-magnitude, a different and older convention, and the two disagree from the very first value: $10000001_2$ is $-1$ in sign-magnitude but $-127$ in two's complement. Sign-magnitude also has two zeros, $00000000_2$ and $10000000_2$, and it breaks ordinary addition, since adding $00000001_2$ and $10000001_2$ gives $10000010_2$, which sign-magnitude reads as $-2$ instead of $0$. Corrected statement: in two's complement the leading bit is a normal positional digit whose weight is $-2^{n-1}$, negative rather than positive, which is exactly what lets one adder serve both signs.

$\text{0F0}_{16} = 0000\,1111\,0000_2$. Bit $11$ is $0$, so the value is positive and equal to its unsigned reading: $\text{0F0}_{16} = 240$ counts. Temperature: $240/16 = 15.0\ ^\circ$C. Reading the sign bit before anything else is the habit to build here, because the conversion that follows is different in the two cases and looks equally reasonable either way.

$\text{F60}_{16} = 1111\,0110\,0000_2$, and bit $11$ is $1$, so the value is negative. On 12 bits the wheel has $2^{12} = 4096$ patterns, so the signed value is $3936 - 4096 = -160$ counts. Temperature: $-160/16 = -10.0\ ^\circ$C. The trap is to subtract $65536$ instead of $4096$: the field is 12 bits wide, and the wheel size is fixed by the field, not by the variable that will later hold it.

The correct 16-bit pattern is $\text{FF60}_{16} = 1111\,1111\,0110\,0000_2$. The four leading bits are copies of the sign bit, which is sign extension. The check is arithmetic, not visual: as unsigned, $\text{FF60}_{16} = 65376$, and $65376 - 65536 = -160$, the same value as on 12 bits. Widening a signed number must preserve its value, and only replicating the sign bit does that.

Filling with zeros gives $\text{0F60}_{16} = 3936$, a positive number, so the system reports $3936/16 = 246.0\ ^\circ$C. A probe sitting at $-10\ ^\circ$C is reported at $246\ ^\circ$C. Nothing raises an error: the arithmetic is valid, the variable is in range, the reading is simply false. On a freezer controller this trips the over-temperature alarm and starts a cooling cycle that is not needed; on a furnace it does the opposite. Note that the bug is invisible in testing as long as the bench temperature stays positive.

A 16-bit signed accumulator holds at most $2^{15}-1 = 32\,767$. With $200$ readings of up to $2047$ counts, the true sum reaches $200 \times 2047 = 409\,400$, more than twelve times the capacity, so it overflows. For a width $n$ we need $2^{n-1}-1 \ge 409\,400$; since $2^{18}-1 = 262\,143$ is too small and $2^{19}-1 = 524\,287$ is enough, the smallest workable width is $n = 20$ bits. In practice the accumulator is declared as 32-bit, both because $20$ is not a machine width and because it leaves room if the sample count grows.