S5-2.1 Data Representation & Computer Arithmetic

What this is and why it exists

A processor holds numbers as patterns of bits. It has no idea what those patterns mean. The meaning comes from a convention you choose, and the arithmetic hardware is built to match that convention.

This topic sets both. It fixes how numbers are stored, and it shows how addition, multiplication and division are done as hardware rather than as mathematics.

The vocabulary

• Functional units — the parts every machine has: input, output, memory, arithmetic and logic, and control.
• Fixed point — a representation with the binary point at an agreed, unmoving position.
• Two's complement — the usual signed convention. Negate a number by inverting every bit and adding one.
• Overflow — the result of an operation does not fit the register it must go in.
• Booth's algorithm — a signed multiplication method that recodes runs of ones into one subtraction and one addition.
• Restoring division — trial subtraction, and if the result goes negative, add the divisor back.
• Non-restoring division — the same trial, but a negative result is carried forward instead of undone.
• Floating point — a sign, an exponent and a fraction, so the point can move.
• IEEE 754 — the standard that fixes the field widths and the rules for floating point.

The mental model

Start with the map of the machine. Input brings data in, memory holds it, the arithmetic and logic unit works on it, output sends results away, and control decides the order. Every later topic sits inside one of those five boxes. Return here whenever a detail feels like it is floating free of anything physical.

Now the numbers. In fixed point the binary point never moves, so a bit pattern means exactly what the agreed position says it means. Two's complement is the convention almost every machine uses for signed values. Its advantage is that one adder handles both addition and subtraction. To subtract, negate the second operand and add. Negating means inverting every bit and adding one. Overflow is the case worth watching: adding two numbers of the same sign and getting the opposite sign means the answer did not fit.

Multiplication as repeated addition is correct and slow. Booth's algorithm is the improvement, and it is the centrepiece of this topic because it shows arithmetic as hardware. A long run of ones in the multiplier means many additions. But a run of ones is one number minus another. So the run needs only one subtraction at its start and one addition past its end. Booth's algorithm finds those runs by looking at bit pairs as it scans. It also handles signed numbers without a special case. Work an example by hand with real bit patterns, or it will not stick.

Division is trial and error made systematic. Shift, subtract the divisor, and look at the sign. In restoring division a negative result means the trial failed, so you add the divisor back before continuing. Non-restoring division skips that undo. It carries the negative remainder forward and adds instead of subtracting on the next step. The result is the same, with one operation fewer per failed trial, which is exactly what its name says. Trace both on the same pair of numbers and the difference stops being a definition.

Floating point moves the binary point. A number is stored as a sign, an exponent and a fraction. IEEE 754 fixes the widths and the rules. In single precision there is one sign bit, eight exponent bits and twenty-three fraction bits. The exponent is stored with a bias, so it needs no sign of its own. The standard also reserves patterns for zero, for infinity, and for results that are not a number.

That last part has a life beyond the examination. Most decimal fractions have no exact binary form, so a stored value is usually a rounding of the one you typed. Comparing two floating point results for exact equality is therefore unreliable in every language you will write in. Compare against a tolerance instead.

What you should now be able to explain or do

Name the five functional units and place any later topic inside one of them. Convert between signed conventions and detect overflow in two's complement addition. Work Booth's algorithm by hand and explain why a run of ones costs only two operations. Trace restoring and non-restoring division on the same numbers and say which does less work. Lay out an IEEE 754 single precision number and explain why exact equality comparisons are unsafe.

Check yourself