In this topic we'll build on the binary concepts from an earlier module. The lecture segments will discuss how negative numbers are represented in binary, what sort of outcomes may result from binary addition and subtraction, and how binary multiplication works.
The earlier binary discussion dealt only with positive integers. How do we represent negative integers in binary?
A reasonable guess might be to simply reserve one bit to be a + or - sign, perhaps using 0 to represent + and 1 to represent -. We could use the MSB for this, with the remaining bits representing the magnitude of the number. For instance, if we have just 8 bits to work with, then +42 would be:
0 0101010
and -42 would be:
1 0101010
This is called sign magnitude notation, and in later lectures on floating point we'll see one use of it. But, it's suboptimal for integers. For example, under sign-magnitude, the value 00000000 represents zero, and 10000000 represents "negative zero", giving two different ways to represent the same value. This makes testing for a zero complicated. And the circuitry to do addition and subtraction under sign magnitude rules is more complex than necessary.
A better, though initially a bit surprising, approach is called two's complement notation, and this is what almost all computers use for negative integers.
Two's complement is best understood by considering a cyclic or "modular" view of counting.
Let's start with an example familiar to most drivers. Almost all cars have odometers, which show the number of kilometers (or miles) thus far driven on the car. In modern cars, these are typically six digits, and thus go up to 999,999.
If we imagine an especially long-lived car that reaches that figure, what happens if we drive it another kilometer? The odometer returns to 000,000. Mathematicians call a number system that "wraps back to zero" after a given value a modular arithmetic, and the odometer is an example.
Given this modular, or wrap-back-to-zero, behavior, one could make a reasonable argument that 999,999 on an odometer actually represents -1, since adding 1 to it results in 0. By the same reasoning, 999,998 could be viewed as -2, since it's two kilometers "less" than 0. And so on.
To be sure you have the idea, what odometer reading would equate to -50? How about -250?
Answer 1
So, is this just a clever game, or would such a representation for -1, -2, etc actually work in general computations?
Answer 2
So, in that example, and in others, 999,998 does act like -2.
OK, so how far back do we take this? Does 999,000 represent -1000? Does 600,000 represent -400,000? Yes. The standard approach with such systems is to divide the range in half, with the upper half (500,000 and higher) being viewed as less than zero, or negative.
So how does this all work in binary numbers instead of odometers? Let's try it with 8 bits, to keep the values small. As you may recall from earlier lecture, counting upward in 8 bits ultimately reaches the value 1111111, or 255. And in almost all computer hardware, adding 1 to 11111111 flips the value back to 00000000, just like a small binary car odometer. So, we can view 11111111 as effectively -1, 11111110 as -2, etc.
This is how two's complement notation works. We take advantage of the fact that binary addition is modular in computer hardware, and we consider all values in the top half of a binary range to be negative.
Answer 3
Instead of counting from 0 to 255 in 8 bits, we count from -128 to 127. Either way we have 256 possible values; they're just distributed differently under two's complement.
Note also that all the negative values, starting with 1000000, have a 1 in their MSB. So we can test for negativity by checking the MSB.
In sign-magnitude notation the MSB also indicates positive/negative. Does that mean two's complement and sign-magnitude are the same?
Answer 4 No. For instance 11111111 in sign-magnitude represents -127, not -1
Whether 11111111 is -1 or 255 is really a question of viewpoint. Importantly, the hardware is OK with either view. Like the car odometer, binary addition circuits in a CPU simply add binary values, wrapping back to zero. It's up to you whether you see the patterns as all positive, or half negative. This is a major reason for the popularity of two's complement; there's no need for any change to the hardware for it to work.
The terms unsigned and signed are often used to describe the positive-only view, or the two's complement view, respectively. We'll use these from now on.
All this translates naturally to larger integers. More bits simply give you larger number ranges. With 16 bits, the unsigned values go from 0 to 65,535, and the signed (or two's complement) go from -32,768 to 32,767. With 32 bits, the unsigned and signed ranges are 0 to 4,294,967,295 and -2,147,483,648 to 2,147,483,647, respectively.
In all cases, there is one more value in the negative direction that the positive one. It's -128 to 127 in 8 bits, or -32768 to 32767 in 16 bits. There's no way to avoid this. Since 0 is neither positive nor negative, that leaves an odd number of possible nonzero values, and it's most convenient to make the halfway point negative instead of positive since then all negative values have an MSB of 1. The result is a slight skew in favor of the negative range.
Converting between a positive and negative binary number under two's complement can be done via a simple trick:
Invert all the bits, and add 1
For instance, let's convert binary +3 (00000011) to binary -3 (1111101). First, we invert the bits, changing all 1-bits to 0-bits, and vice versa:
00000011 => 11111100
Then we add 1:
11111100 => 11111101
Answer 5
11111101 => 00000010 => 00000011
So, why does this work? Consider the diagram here of the positive and negative values surrounding 0:
5 00000101 4 00000100 3 00000011 2 00000010 1 00000001 0 00000000 ------------- -1 11111111 -2 11111110 -3 11111101 -4 11111100 -5 11111011
Note that inverting the bits matches values across the dashed line between 0 and -1. Bit-inverted pairs are 0<->-1, 1<->-2, etc. Bit inversion is not symmetrical around 0; it's symmetrical around the line between -1 and 0. Thus, inverting bits in either direction gives a value that is 1 less than the desired negative, e.g. 1 converts to -2 but we want -1, and -2 converts to 1 but we want 2. We compensate by adding 1 to get the correct negated value.
Many texts introduce this trick as the definition of two's complement, but that's neither intuitive nor useful. Two's complement is about using modular or cyclic arithmetic to arrive at an elegant definition of negative numbers that works without changing existing hardware. The invert-and-add-one trick is just a useful algorithm for doing negation under two's complement.
Our little thought-experiment with the odometer, treating 999,999 as a -1, actually has an interesting history, and a formal name: ten's complement. Charles Babbage, recognized as an early inventor of mechanical-form computers in the 19th century, used tens complement in his computers, and it was used more recently in the Curta calculator, a renowned handheld calculating device of the mid 20th century.