Two's Complement Arithmetic
The on-and-off voltages manipulated inside a digital computer are, by convention, usually interpreted as "ones" and "zeroes." Strings of ones and zeroes are, by a further act of interpretation, usually held to represent larger numbers. However, no one system of interpretation is mandatory. For example, "0000" is always, in practice, read as decimal 0, and "0001" as decimal 1, but it could have been the other way around. Any mapping of voltages to numbers is, ultimately, arbitrary.
There are practical consequences to this freedom of interpretation. Consider the question of representating positive and negative integers using N bits. N bits allow for 2N different orderings of ones and zeroes. How should one interpret each of these 2N strings? There are three basic answers: (1) the sign-and-magnitude (S&M) system, (2) the radix complement system (of which two's complement arithmetic is a special case), and (3) the digit complement system. The first two are discussed below; a version of the third, the one's complement system, is also used in computers but will not be described here.
The S&M system is the most intuitive. In it, one interprets the leftmost (most significant) bit not as "1" or "0" but as "+" or "-." (By convention, the same physical device state is used for "0" and for "+.") One uses the remaining N-1 bits to represent positive magnitudes; for example, if N = 5 then the 4 digits to the right of the sign bit are interpreted as 0001 = 1, 0010 = 2, 0011 = 3, and so on. In this system, 00001 = +1 (leading 0 specifies plus sign), 10001 = -1 (leading 1 specifies minus sign), and so on. The S&M system has the peculiarity that there are two zeroes, a positive zero and a negative zero (00000 and 10000, respectively, for 5-bit word length)--two distinct binary numbers which are computationally equivalent.
Consider the addition of two S&M numbers, say +2 and -10:
0 0 0 1 0 [2] + 1 1 0 1 0 [-10] ————- 1 1 0 0 0 [-8]
It is notable here that the simplest way of adding the operands (i.e., bit by bit, starting with the rightmost, or least significant, bit) would produce a wrong answer, namely 11100 (-12). On the other hand, adding +2 and positive 10 proceeds as follows:
0 0 0 1 0 [2] + 0 1 0 1 0 [10] ————- 0 1 1 0 0 [12]
Here the correct result is achieved by ordinary bitwise addition starting with the least significant bit. It follows that when performing addition in the S&M system, one must apply different addition rules to the individual bits of the operands depending on their signs. This increases complexity--more hardware or more computation or both. Since binary multiplication and division of integers are achieved by repeated additions, the need for a more complex adder circuit affects the other basic numerical operations as well. Is there a number system that allows use of the same rules for any two numbers?
There are at least two such. The one in almost universal usage is the two's complement system, which may be understood in terms of modulo arithmetic--that is, arithmetic which uses a closed or circular number system. A familiar example of such a system is the numbering of the hours on an analog clock face.
Imagine the face of a clock with its numbers in the usual places, only with a 0 at the top instead of a 12. As an adder, such a clock has odd properties. Two o'clock plus 3 hours is five o'clock (2 + 3 = 5), but ten o'clock plus 3 hours is one o'clock (10 + 3 = 1?). In the latter case, adding a relatively large number actually has the effect of a subtraction--of adding a negative number. This property can be used to advantage as follows.
Define all the hours from 0 to 5 literally—that is, let 2:00 stand for +2, 3:00 for +3, and so on. The rest of the clock shall be used to represent negative numbers. Consider what happens if we declare that 11:00 codes for -1. To add -1 to 3 we would then physically add 11 to 3, which means starting at 3:00 and moving 11 hours clockwise to 2:00. This gives the correct answer (-1 + 3 = 2). (If this not clear to your mind's eye, sketch a clock.) All the hours later than 5:00 can be used to "code" for negative numbers in this fashion as follows:
-1 = 11:00
-2 = 10:00
-3 = 9:00
-4 = 8:00
-5 = 7:00
-6 = 6:00
Each number on the dial thus has a complement or negative version of itself on the other side. (The exceptions are 0, which needs no complement, and -6, which has none in this system.) Note that the numbers to be physically added are always the hours themselves, and that all additions are performed by the same physical process, namely clockwise movement around the dial, which recalls our desire to use only one kind of adding mechanism in the digital realm. Note also that in this system no additions are valid that give results greater than 5 or less than -6; for instance, "5 + 4 = 9" cannot be calculated on this very crude processor because there is no way to represent a 9. (9:00 is reserved to code for -3.) In digital computing, any such attempt to produce a non-representable result is called an overflow.
To avoid overflow in practical computations, we need a bigger clock. This is exactly, in effect, what the two's complement number system provides. In the two's complement system, all 2N binary numbers are treated (in effect) as if they were arranged around a vast clock face, starting with 0 at noon and continuing clockwise in order of magnitude. Half these 2N numbers (those with a "1" for most significant bit) occupy the space from 6:00 to noon and are defined as negative. Arithmetic proceeds exactly as in the 12-hour system described above, only with many more numbers (for a 32-bit word, over 4 billion numbers). Just as the most negative number on the clock (-6) had no positive complement, the most negative number in two's complement has no positive complement. In the binary system, too, just as on the clock, the same procedures apply to adding all numbers, whether positive or negative. Note that in two's complement representation the most significant bit of every word can (as in the S&M system) be viewed as a sign bit, in the sense that every number with a leading 1 is negative. However, to change a number from positive to negative or vice versa it does not, in two's complement, suffice to reverse its sign bit.
The two's complement of a binary number may be produced very simply, in hardware or by hand, without resorting to visualizations of clocks or circular number systems. Given a binary number M, start with the rightmost bit and copy all bits up to and including the first 1 encountered; then complement (flip from 0 to 1 or vice versa) all the remaining bits. The two's complement of 010110, for example, is obtained as follows:
Reversing the sign of a number thus is more complex in the two's complement system than in the S&M system (where flipping the sign bit is all that is necessary). However, sign reversal can still be accomplished in a single clock cycle by a simple circuit.
Because the computational tasks involved in manipulating floating-point numbers are different from those for manipulating fixed-point numbers, such as the integers treated above, two's complement is not used to code floating-point numbers.
This is the complete article, containing 1,264 words
(approx. 4 pages at 300 words per page).
