Number Representation & Computer Arithmetic

Digital Logic contributes a steady share of the core-CS marks, and number representation is the part that reaches furthest: it decides how the ALU is built, why floating-point comparisons fail, and what an overflow flag actually detects.

A bit pattern carries no meaning by itself. The sequence 1111 1111 is 255 as an unsigned integer, $-1$ in two's complement, $-127$ in sign-magnitude, and something else entirely as part of a floating-point field. The representation supplies the meaning, and every question in this chapter is really asking what one pattern means under a stated reading.

The second principle is that every representation has a finite range, and questions live at the boundary. Overflow, the asymmetry of the two's complement range, and the loss of precision in floating point are all consequences of running out of bits, and none of them are accidents.

So the method is: fix the representation, compute the range, and check whether the operation stays inside it. That single habit answers most of the examinable material.

1. Positional Systems and Base Conversion

In base $r$, the digit at position $i$ contributes its value multiplied by $r^i$, with positions counted rightwards from zero and fractional positions taking negative exponents.

Converting from base $r$ to decimal is direct expansion. Converting decimal to base $r$ splits into two halves that use opposite operations.

The integer part is converted by repeated division, reading remainders bottom-up. The fractional part is converted by repeated multiplication, reading the integer overflows top-down.

Mixing the two directions is the standard error. The remainders of the integer part come out least significant first, so they are read in reverse; the overflows of the fraction come out most significant first, so they are read in order.

Between binary, octal and hexadecimal, no arithmetic is needed at all. Group bits in threes for octal and in fours for hexadecimal, starting from the binary point and padding outward.

A decimal fraction that terminates need not terminate in binary. One tenth is $0.0\overline{0011}$ in binary, repeating forever, which is the root cause of most floating-point surprises.

2. Signed Integer Representations

Three schemes appear, and they differ in how the negative half of the range is encoded.

Two's complement is used universally because it has a single zero and because subtraction is addition of the negation, so one adder circuit serves both operations. The other two schemes require end-around carry or separate hardware.

The range is asymmetric: for 8 bits it runs from $-128$ to $+127$. The most negative value has no positive counterpart, so negating it overflows and returns itself, which is a favourite examination point.

A useful shortcut for reading a two's complement number: the most significant bit carries weight $-2^{n-1}$ while all other bits carry their usual positive weights. So 1011 in 4-bit two's complement is $-8+0+2+1=-5$.

Sign extension preserves value when widening. Copy the sign bit into every new high-order position: 1011 extends to 1111 1011, both representing $-5$. Zero-filling instead would give 251.

The two complement schemes generalise to any base, and the general names are worth knowing because questions sometimes pose them in base 10.

The $r$'s complement of a number in base $r$ is $r^n$ minus the number; the $(r-1)$'s complement is $r^n-1$ minus it, which is obtained digit by digit without any borrow.

In binary these are the two's and one's complements. In decimal they are the 10's and 9's complements, so the 9's complement of 462 is 537, obtained by subtracting each digit from 9, and the 10's complement is 538.

The relationship is uniform: the $r$'s complement is always the $(r-1)$'s complement plus one, which is exactly the rule used for two's complement in binary.

3. Two's Complement Arithmetic and Overflow

Addition proceeds identically for signed and unsigned operands — the same adder, the same carries. What differs is how overflow is detected.

Unsigned overflow is signalled by a carry out of the most significant bit. Signed overflow is signalled by the carry into the sign position differing from the carry out of it.

An equivalent and more memorable test: signed overflow occurs exactly when two operands of the same sign produce a result of the opposite sign. Adding two positives cannot legitimately give a negative.

It follows that adding numbers of opposite signs can never overflow, because the magnitude of the result is no larger than the larger operand.

Subtraction is performed as $A+\overline{B}+1$, that is, adding the two's complement of $B$. The same overflow rules then apply to the addition that actually takes place.

A carry out is not an error in unsigned arithmetic if the result is being interpreted modulo $2^n$, which is exactly what happens in address arithmetic. Whether a carry is an overflow depends on the interpretation, not on the hardware.

4. Multiplication and Division

Unsigned multiplication of two $n$-bit numbers produces a $2n$-bit product, which is why hardware multipliers write to a double-width register pair.

Booth's algorithm multiplies signed numbers directly in two's complement without converting to magnitudes, and it accelerates operands containing runs of ones.

The mechanism is to recode a run of ones as a subtraction at the start of the run and an addition just past its end, since a block of $k$ ones equals $2^k$ minus 1 in that position. A string of eight ones becomes one subtraction and one addition rather than eight additions.

Booth's algorithm inspects a pair of bits — the current bit and the one to its right — and acts on the transition, with a phantom zero appended below the least significant bit to start the process.

Restoring and non-restoring division are the two examined division algorithms. Restoring division subtracts the divisor and, if the result goes negative, adds it back; non-restoring skips the restore and compensates on the next step, trading a conditional add for a fixed number of steps.

5. Floating Point and IEEE 754

Fixed-point representation places the binary point at a fixed position, giving uniform absolute precision but a narrow range. Floating point moves the point, trading uniform precision for enormous range.

A floating-point number is stored as a sign, a biased exponent and a fraction:

$V=(-1{)}^S\times 1.M\times 2^{E-\text{bias}}$

The leading 1 is not stored. Normalisation guarantees exactly one non-zero digit before the point in binary, and since that digit can only be 1, it is implicit and buys one extra bit of precision for free.

The exponent is biased rather than stored in two's complement so that the bit patterns compare in the same order as the numbers themselves, which lets integer comparison hardware compare positive floats directly.

Two exponent values are reserved and never used for normalised numbers.

Denormals fill the gap between zero and the smallest normalised number by dropping the implicit leading 1, at the cost of reduced precision — a phenomenon called gradual underflow.

6. Precision, Rounding and Comparison

The exponent controls range and the fraction controls precision, and they trade against each other for a fixed word size. Moving a bit from fraction to exponent widens the range and coarsens the resolution.

Single precision carries 24 significant bits including the implicit one, which is about 7 decimal digits. Double precision carries 53, about 16 decimal digits.

Machine epsilon is the gap between 1.0 and the next representable number, which is $2^{-23}$ for single precision and $2^{-52}$ for double. It is the relative resolution, not an absolute one: the spacing between consecutive floats doubles with every increase in the exponent.

Three consequences are examined directly.

Floating-point addition is not associative. Adding a tiny number to a huge one loses the tiny one entirely, so the order of summation changes the result. This is why summing a large array in different orders gives different answers.

Testing floating-point values for exact equality is unreliable, because values such as 0.1 have no exact binary representation, so 0.1 added three times does not equal 0.3. Comparisons use a tolerance instead.

Subtracting two nearly equal numbers destroys precision, a phenomenon called catastrophic cancellation: the leading significant digits cancel and the result is dominated by whatever rounding error was already present.

IEEE 754 defines four rounding modes, and the default is the one candidates least expect.

Ties are broken toward the even last bit rather than always upward, because always rounding halves up introduces a systematic upward bias across a long computation, while ties-to-even cancels on average.

7. Codes

Not every binary code is a positional number system, and several exist for reasons other than arithmetic.

Binary Coded Decimal stores each decimal digit in its own group of 4 bits, so 29 becomes 0010 1001. It wastes the six patterns from 1010 to 1111 and requires a correction of adding 6 when a sum exceeds 9, but it makes decimal input and output exact — which is why it survives in financial and display hardware.

Gray code changes exactly one bit between consecutive values, which is what makes it useful for position encoders and for K-map adjacency. A transition that changed several bits at once could be sampled mid-change and read as a wildly wrong value.

Converting binary to Gray code exclusive-ORs each bit with the bit above it, keeping the most significant bit unchanged. Converting back accumulates the exclusive-OR from the top down.

Excess-3 is a self-complementing code in which the 9's complement of a digit is obtained by inverting the bits, which simplified decimal subtraction in early hardware.

8. Worked Examples

Example 1. What decimal value does the 8-bit pattern 1001 0110 represent in unsigned, sign-magnitude, 1's complement and 2's complement?

Unsigned: expand positionally. $128+16+4+2=150$.

Sign-magnitude: the leading 1 marks it negative and the remaining bits 001 0110 give $16+4+2=22$, so the value is $-22$.

1's complement: negative, so invert all bits to recover the magnitude. 0110 1001 is $64+32+8+1=105$, so the value is $-105$.

2's complement: use the negative-weight shortcut. The leading bit carries $-128$, and the rest contribute $16+4+2=22$, giving $-128+22=-106$.

Four different values from one pattern, which is the point of the exercise. Note that the 1's complement and 2's complement answers differ by exactly 1, as they always do for negative values.

Example 2. Add the 8-bit two's complement numbers 0110 1100 and 0101 0011. Does signed overflow occur?

Add the patterns bitwise: $01101100+01010011=10111111$.

Now check the signs. Both operands begin with 0, so both are positive: 108 and 83, whose true sum is 191.

The result begins with 1, so it reads as negative in two's complement — specifically $-65$.

Two positive operands cannot legitimately produce a negative result, so signed overflow has occurred.

Confirm with the carry rule: the carry into the sign position is 1 while the carry out is 0, and the disagreement is exactly the overflow condition.

Note that as an unsigned addition there is no problem: 108 plus 83 is 191, and 1011 1111 is 191. Whether this is an error depends entirely on the interpretation.

Example 3. Represent $-6.75$ in IEEE 754 single precision.

Convert the magnitude to binary. The integer part 6 is 110; the fraction 0.75 is .11 since $0.5+0.25=0.75$. So $6.75=110.11_2$.

Normalise: move the point left two places to get $1.1011\times 2^2$.

The sign bit is 1 because the number is negative.

The exponent field is the true exponent plus the bias: $2+127=129$, which is 1000 0001 in 8 bits.

The fraction field is the digits after the implicit leading 1, padded to 23 bits: 1011 followed by nineteen zeros.

Assembled: 1 10000001 10110000000000000000000.

The implicit leading 1 is what makes the fraction field start at 1011 rather than 11011, and forgetting to drop it is the commonest error in this conversion.

Example 4. What is the range of an 8-bit two's complement number, and what happens when the most negative value is negated?

The range is $-2^7$ to $2^7-1$, that is, $-128$ to $+127$.

Negate $-128$, whose pattern is 1000 0000. Invert all bits to get 0111 1111, then add 1 to get 1000 0000.

The result is the same pattern, so negating $-128$ gives $-128$.

This is not a bug in the procedure but a consequence of the asymmetric range: $+128$ simply does not exist in 8-bit two's complement, so the negation has nowhere to land and overflows.

The asymmetry exists because two's complement has a single zero. With $2^8=256$ patterns, one is spent on zero, leaving 255 to split between positives and negatives, and the split cannot be even.

Example 5. Multiply $-5$ by $3$ using Booth's algorithm with 4-bit operands.

Represent $-5$ as the multiplicand $M=1011$ and $3$ as the multiplier $Q=0011$, and append a phantom bit $Q_{-1}=0$.

Examine the bit pair $(Q_0,Q_{-1})$ at each step, act, then arithmetic-shift right.

Step 1: pair is $(1,0)$, so subtract $M$, then shift. Subtracting $-5$ means adding 5.

Step 2: pair is $(1,1)$, so shift only.

Step 3: pair is $(0,1)$, so add $M$, then shift. Adding $-5$.

Step 4: pair is $(0,0)$, so shift only.

The product is $-15$, correct as an 8-bit two's complement result.

The efficiency point is visible in step 2: the run of ones in the multiplier 11 required only the boundary operations at its two ends, not one addition per one-bit.

Example 6. Why does 0.1 + 0.2 == 0.3 evaluate to false in floating-point arithmetic?

Because none of the three values is exactly representable in binary.

One tenth in binary is $0.0\overline{0011}$, an infinitely repeating expansion, exactly as one third is infinitely repeating in decimal. It must be truncated to fit the 23-bit fraction field.

So the stored value for 0.1 is slightly more than one tenth, and the stored value for 0.2 is likewise inexact.

Their sum is then rounded again to the nearest representable value, and that value happens to differ in the last bit from the stored approximation of 0.3.

Two consequences follow. Floating-point equality should be tested against a tolerance rather than exactly. And because each addition rounds, the operation is not associative: summing a long array left to right and right to left can give different totals, with the difference growing when the magnitudes vary widely.

Summary

A bit pattern means nothing without a stated representation, and one pattern reads as four different values under unsigned, sign-magnitude, 1's complement and two's complement.

Convert integers by repeated division reading upward, and fractions by repeated multiplication reading downward. Group bits in threes for octal and fours for hexadecimal.

Two's complement wins because it has one zero and turns subtraction into addition. Its range is asymmetric, so negating the most negative value overflows.

Sign extension copies the sign bit; zero-filling a negative number changes its value.

Unsigned overflow is a carry out; signed overflow is a disagreement between the carry in and carry out of the sign position, equivalently two same-signed operands producing an opposite-signed result.

Booth's algorithm multiplies two's complement operands directly and collapses runs of ones into two boundary operations.

IEEE 754 stores sign, biased exponent and fraction, with the leading 1 implicit. Single precision uses 8 exponent bits with bias 127 and 23 fraction bits; double uses 11 with bias 1023 and 52.

All-zero and all-one exponents are reserved for zero, denormals, infinity and NaN.

The exponent buys range and the fraction buys precision. Floating-point addition is not associative, exact equality is unreliable, and subtracting nearly equal values destroys significance.

BCD makes decimal exact at the cost of wasted patterns; Gray code changes one bit at a time, which is why it suits encoders and K-map adjacency.