Binary arithmetic and signed integers
Introduced| English | Meaning |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | A condition in which a result exceeds the range representable by the available storage or number format. |
| two's complement/tuːz ˈkɒmplɪmənt/ | A signed binary integer representation in which a negative value is formed by inverting the positive value's bits and adding one within a fixed bit width. |
| register/ˈredʒɪstə/ | A small, fast storage location within a processor used to hold data, addresses or instructions temporarily. |
| sign bit/saɪn bɪt/ | The bit in a signed-number representation that indicates or contributes the number's sign. |
| most significant bit/məʊst sɪɡˈnɪfɪkənt bɪt/ | The bit with the greatest positional weight in a binary number. |
| one's complement/wʌnz ˈkɒmplɪmənt/ | A signed binary representation in which a negative value is formed by inverting every bit of its positive counterpart. |
| Binary Coded Decimal/ˈbaɪnəri ˈkəʊdɪd ˈdesɪml/ | Binary Coded Decimal |
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
Binary & signed integers
byte = Σ place values
See how an 8-bit pattern maps to a number (and how it would overflow past 255).
Add the binary numbers 0101 + 0011. Give the 4-bit result.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
$5 + 3 = 8$, which is 1000 in binary.
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.
Overflow in binary addition means:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Overflow occurs when the sum is too large to fit in the available bits; the carry out of the leftmost column is lost.
Worked example: name the overflow properly
- Add the 8-bit unsigned integers
10110101and01101100and comment on the result. - The sum is
1 0010 0001, which needs 9 bits. The true result is 289. - Full answer: overflow has occurred, because 289 is larger than the largest value an 8-bit register can hold, 255; the carry out of the most significant bit is lost, so the stored result
0010 0001is 33, which is wrong. - The mark is for naming the register width and saying the result cannot be represented in it. "The answer was more than 255" alone does not score.
Two 8-bit unsigned integers are added and the result needs 9 bits. Which is the full-mark explanation?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Name the register width, say the result cannot be represented in it, and say what happens to the carry. The other options state a symptom without the cause.
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 1110is1110 0001inverted, plus 1, so1110 0010. 0110 0100$+$1110 0010$=$1 0100 0110; discard the leading 1 and read0100 0110$= 70$. ✓
Subtraction becomes addition, which is why processors need no subtractor
What is the 4-bit two's complement of 0011? (invert, then add 1)
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Invert 0011 → 1100, then add 1 → 1101 (which represents $-3$).
Put the steps of subtracting B from A by two's complement in order.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
Invert, add one, add, discard. The discard is what keeps the answer in the register's width.
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 0100inverts to0100 1011, plus 1 is0100 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
Two's complement signed bits
The leftmost bit carries a negative place value. Flip any bit — or hit Negate (invert every bit, then add 1) — and watch the signed value change.
Read the 8-bit two's complement number 11111101 as a signed denary value.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
MSB is 1 (negative). Invert → 00000010, add 1 → 00000011 $= 3$, so the value is $-3$.
What is the largest positive value an 8-bit two's complement number can hold?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Range is $-2^{7}$ to $2^{7}-1$, i.e. $-128$ to $+127$. The maximum is 01111111 = 127.
Worked example: write −108 in 12 bits
- Start from $+108$ in 12 bits: $108 = 64 + 32 + 8 + 4$, so
0000 0110 1100. - Invert every bit:
1111 1001 0011. Add 1:1111 1001 0100. - Check with place values, where the top bit is worth $-2048$: $-2048 + 1024 + 512 + 256 + 128 + 16 + 4 = -108$. ✓
- The commonest error is sign and magnitude: setting the top bit to 1 and leaving the rest. That is a different, older scheme and scores zero here.
Write −108 as a 12-bit two's complement number (spaces allowed).
Difficulty 1/5 · 100 coins + a small bonus on first completion today
+108 is 0000 0110 1100; invert to 1111 1001 0011 and add 1. Check: −2048 + 1024 + 512 + 256 + 128 + 16 + 4 = −108.
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$ is1110 0001. - Its drawback is two zeros,
0000 0000and1111 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.
One's complement is preferred to two's complement because it has only one representation of zero.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The opposite: one's complement has two zeros, +0 and −0. Two's complement has one, and lets the adder do subtraction.
Binary Coded Decimal
- In Binary Coded Decimal 二进制编码十进制 (BCD) each denary digit is stored as its own 4-bit pattern, using only
0000to1001. - 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
1010to1111are never used.
One digit, one nibble, one display
Write the denary digit $9$ as a 4-bit BCD pattern.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
$9$ is 1001. In BCD each denary digit gets its own nibble (0000–1001).
Match each bit pattern to what it represents.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Nothing in the bits says how to read them. The agreed representation decides the value.
Marks that slip away
- Explain overflow with the register width the question gave, not with "it was more than 255".
- To negate, invert and add 1. Setting the top bit to 1 is sign and magnitude, a different scheme.
- Two's complement subtraction ends by discarding the final carry-out. Keeping it gives a nine-bit answer.
- BCD stores each digit separately; pure binary stores the whole number.
1001 0011is 93 in BCD and 147 in binary.
You've got it
- add column by column with carries; overflow is a result needing more bits than the register holds, and the answer names that width
- subtract by adding the two's complement, invert and add 1, then discard the final carry
- signed: the MSB is the sign bit and carries $-2^{n-1}$; range $-2^{n-1}$ to $+2^{n-1}-1$; read a negative by inverting, adding 1 and negating
- one's complement inverts only and has two zeros; BCD stores each denary digit in its own nibble, for clocks, calculators and currency