二進算術および符号付き整数

The bank that lost a day

• On 1 September 1983 the Vancouver Stock Exchange index stood at 524.811. It had opened at 1000 twenty-two months earlier, and the market had risen the whole time.
• The program recalculated the index after every trade, truncating rather than rounding each time. Each truncation lost a fraction of a point. Three thousand trades a day did the rest.
• When it was recomputed properly the index was 1098.892: the arithmetic, not the market, had halved it.
• Arithmetic on a fixed number of bits is not the arithmetic you learned at school. This lesson is binary addition, overflow 溢出, subtraction by two's complement 补码, signed integers, and BCD.

Binary addition

• Add column by column from the right, carrying into the next column, exactly as in denary.
• The rules: $0 + 0 = 0$; $0 + 1 = 1$; $1 + 1 = 10$, write 0 and carry 1; $1 + 1 + 1 = 11$, write 1 and carry 1.
• 0101 $+$ 0011 $=$ 1000, that is $5 + 3 = 8$.

Same method as denary, only two digits to carry between

Overflow

• Overflow happens when the result of a calculation needs more bits than the register 寄存器 can hold. The carry out of the most significant column is lost, so the stored answer is wrong.
• It is a property of the register width, not of the number 255: in a 16-bit register the same sum is fine.
• In signed arithmetic the tell-tale is a sign bit that flips wrongly: two positives giving a negative, or two negatives giving a positive.

Worked example: name the overflow properly

Subtraction by two's complement

• To calculate $A - B$: form the two's complement of $B$ by inverting every bit and adding 1, add it to $A$, then discard any final carry-out.
• $100 - 30$ in 8 bits: two's complement of 0001 1110 is 1110 0001 inverted, plus 1, so 1110 0010.
• 0110 0100 $+$ 1110 0010 $=$ 1 0100 0110; discard the leading 1 and read 0100 0110 $= 70$. ✓

Subtraction becomes addition, which is why processors need no subtractor

Two's complement signed integers

• In an $n$-bit two's complement number the most significant bit 最高有效位 is the sign bit 符号位: 0 means positive, 1 means negative. Equivalently, the top bit carries a negative place value, $-2^{n-1}$.
• To read a negative number: invert every bit, add 1, then put a minus sign in front. 1011 0100 inverts to 0100 1011, plus 1 is 0100 1100 $= 76$, so the value is $-76$. Check by place value: $-128 + 32 + 16 + 4 = -76$. ✓
• For $n$ bits the range is $-2^{n-1}$ to $+2^{n-1} - 1$: 8 bits give $-128$ to $+127$, 12 bits give $-2048$ to $+2047$. The most negative value is a 1 followed by zeros; the most positive is a 0 followed by ones.

11111111 is 255 read one way and −1 read the other

Worked example: write −108 in 12 bits

One's complement

• One's complement 反码 is the older scheme: a negative is made by inverting every bit of the positive, with no add-1 step. $+30$ is 0001 1110, so $-30$ is 1110 0001.
• Its drawback is two zeros, 0000 0000 and 1111 1111, which wastes a bit pattern and complicates the arithmetic.
• Two's complement has one zero and lets the same adder circuit do subtraction, which is why it won.

Binary Coded Decimal

• In Binary Coded Decimal 二进制编码十进制 (BCD) each denary digit is stored as its own 4-bit pattern, using only 0000 to 1001.
• 93 in BCD is 1001 0011, which is not the same as 93 in pure binary, 0101 1101. Reading one as the other is a favourite exam trap.
• Uses: calculators, digital clocks and seven-segment displays, where each digit is driven separately, and currency, where BCD avoids the rounding errors of storing $0.1$ in pure binary. The cost is wasted patterns, since 1010 to 1111 are never used.

One digit, one nibble, one display

Marks that slip away

You've got it