Computer Science › Section B · Data storage › Topic B.6

Storing integers: two's complement and excess notation

A computer stores each integer in a fixed number of bits, so it needs a rule for which patterns mean negative numbers. Two's complement makes one adding circuit serve for subtraction too, and excess notation keeps patterns in numerical order.

Fixed-width patterns

Processors handle integers in fixed widths, usually 8, 16, 32 or 64 bits. With n bits there are exactly \(2^n\) patterns, and that is all the integers a format can ever hold. If every pattern stands for a non-negative number, the format is unsigned: 8 bits cover 0 to 255. To store negative numbers too, some of the patterns must be given negative meanings. This topic covers the two schemes that matter most today. Two's complement is used for almost all integer arithmetic, and excess notation is used where patterns must sort in numerical order, most importantly for the exponents of the floating-point numbers in the next topic.

Two's complement: a negative leftmost weight

In two's complement, the leftmost bit has a negative weight. For 8 bits the weights are −128, 64, 32, 16, 8, 4, 2 and 1. A pattern starting with 0 is read as ordinary binary, so 01111111 is 127, the largest value. A pattern starting with 1 includes the −128, so 10000000 is −128 and 11111111 is \(-128 + 127 = -1\). The leftmost bit therefore tells you the sign at a glance and is called the sign bit. In general, n bits hold the range

-2^{n-1} \text{ to } 2^{n-1} - 1

There is one more negative value than positive, because zero takes one of the patterns that begin with 0.

Negating a number

To find the pattern for −x from the pattern for x, invert every bit and then add 1. In 8 bits, 5 is 00000101; inverting gives 11111010, and adding 1 gives 11111011, which is −5. A shortcut gives the same result: copy the bits from the right up to and including the first 1, then invert everything to its left. Negating twice returns the original pattern, so the same method decodes a negative number. One pattern is an exception: negating 10000000 gives 10000000 again, because +128 does not fit in 8 bits.

Worked example: encoding and decoding

Encode −45 in 8-bit two's complement. 1. Write 45 in binary with 8 bits: 00101101. 2. Invert every bit: 11010010. 3. Add 1: 11010011. 4. Check with the weights: \(-128 + 64 + 16 + 2 + 1 = -45\). Now decode 11101100. 5. The sign bit is 1, so the value is negative. 6. Negate to find its size: invert to 00010011, add 1 to get 00010100, which is 20. 7. The value is −20. 8. Check with the weights: \(-128 + 64 + 32 + 8 + 4 = -20\). Two methods agreeing is the best evidence you have it right.

Addition, and subtraction for free

The great advantage of two's complement is that signed numbers add with the ordinary binary method. Add the patterns as if they were unsigned, and throw away any carry out of the leftmost column, so the answer keeps the same width. Subtraction needs no circuit of its own: a − b is computed as a + (−b), negating b first. A useful picture is a clock face: the 256 patterns of 8 bits sit in a circle, and 11111111 plus 1 lands back on 00000000 once the carry is dropped, which is exactly −1 + 1 = 0.

Worked example: 50 − 75 in 8 bits

1. Write 50 as 00110010. 2. Write 75 as 01001011 and negate it: invert to 10110100, then add 1 to get 10110101, the pattern for −75. 3. Add the two patterns: 00110010 + 10110101 = 11100111. There is no carry out of the leftmost column this time. 4. The sign bit is 1, so the result is negative. Negate it to find its size: invert to 00011000, add 1 to get 00011001, which is 25. 5. The answer is −25, and 50 − 75 = −25 in decimal. The machine never subtracted; it negated and added.

Overflow

Overflow happens when the true result lies outside the range the format can hold. In 8 bits, 100 + 60 = 160 is too big: 01100100 + 00111100 gives 10100000, which reads as −96. Likewise −100 + (−90) gives 01000010, or 66, once the carry is dropped. The detection rule follows from these: overflow can occur only when both operands have the same sign, and it has occurred exactly when the result's sign differs from theirs. Adding a positive and a negative number can never overflow. Unsigned numbers wrap too: 255 + 1 in 8 bits gives 00000000.

A real limit: the year 2038

Many systems have counted time as a signed 32-bit number of seconds since 00:00:00 UTC on 1 January 1970. The largest such value, 2,147,483,647, is reached at 03:14:07 UTC on 19 January 2038, about 68 years after the start. One second later the count would overflow to the most negative value, which such a clock reads as a date in December 1901. The standard fix is to store time in 64 bits, which pushes the limit billions of years away. The lesson is general: choose a width for the largest value a count could ever reach, not the largest you expect today.

Excess notation

Excess notation, also called biased notation, reads a pattern as ordinary unsigned binary and then subtracts a fixed bias, here \(2^{n-1}\) (IEEE 754 floating point uses one less). With 4 bits the bias is 8, so 1000 means 0, 1101 means 13 − 8 = 5, 0101 means −3, 0000 means −8 and 1111 means 7. To encode, add the bias: in 8-bit excess-128, −37 becomes 91, or 01011011. The big benefit is order: larger values always have larger patterns, so comparing two numbers is a plain comparison of bit patterns. Compared with two's complement, each excess pattern has its leftmost bit flipped: 5 is 0101 in two's complement and 1101 in excess-8.

Common mistakes to avoid

Inverting without adding 1 is off by one: inverting 5 gives 11111010, which is −6, not −5. Reading a pattern with sign bit 1 as unsigned turns −6 into 250. Keeping the final carry adds a ninth bit that the format does not have. Do not confuse that carry with overflow, either: 00001001 + 11111100, which is 9 + (−4), produces a carry out yet gives the correct answer 00000101, or 5. Finally, the bias depends on the width: excess-8 belongs to 4 bits, excess-128 to 8 bits.

Key takeaways

An n-bit format has \(2^n\) patterns. In two's complement the leftmost bit weighs \(-2^{n-1}\), giving the range \(-2^{n-1}\) to \(2^{n-1} - 1\); 8 bits hold −128 to 127. Negate by inverting every bit and adding 1. Add signed numbers with ordinary binary addition, drop the final carry, and subtract by adding the negation. Overflow occurs only when two same-sign operands give a result of the other sign. Excess notation subtracts a bias of \(2^{n-1}\), so patterns sort in the same order as their values.

Flashcards

Flashcard

n-bit format

Exactly 2ⁿ distinct patterns

8 bits give 256 patterns.

Test your understanding

Question 1 of 5

What is −12 in 8-bit two's complement?

Question 2 of 5

Which value does the 8-bit two's complement pattern 11111010 represent?

Question 3 of 5

In 8-bit two's complement, which addition overflows?

Question 4 of 5

What range of values can a 16-bit two's complement integer hold?

Question 5 of 5

In 4-bit excess-8 notation, which value does the pattern 0110 represent?

← Previous topicNext topic →