1. Digital Logic
2. Topic: Representing negative binary numbers

Digital systems have a fixed number of signals that can be used to represent binary numbers. Smaller, simpler systems might use 8-bit buses that can only represent 256 different binary numbers, while larger systems might use 16, 32, or even 64 bit buses. Whatever the number of bits, all systems have a finite number of wires, storage elements, and processing elements to represent and manipulate digital data. The number of available bits determines how many different numbers can be represented in a given system.

Digital circuits that perform arithmetic functions often must deal with negative numbers, so a method of representing negative numbers must be defined. An $N$-bit system can represent $2^N$ total numbers, so a useful encoding would use half the available codes (i.e., $2^N/2$) to represent positive numbers, and half negative numbers. A single bit can be designated as a sign bit to distinguish positive and negative numbers; if the sign bit is ‘1’, the number is negative; if the sign bit is ‘0’, the number is positive. The most-significant-bit (MSB) is a good choice for the sign bit, because if it is a ‘0’ (indicating a positive number), then it can simply be ignored when figuring the number’s magnitude.

Of all possible encodings of negative numbers, two have been used most often: signed magnitude, and 2’s compliment. Signed magnitude representations simply designate the MSB as the sign bit, and the remaining bits as magnitude. In an 8-bit signed-magnitude system, ‘16’ would be represented as ‘00010000’, and ‘-16’ as ‘10010000’. This system is easy for humans to interpret, but it has a major disadvantage for digital circuits: if the 0 to $2^N$ count range is traversed from smallest to largest, then the largest positive number appears halfway through the range, followed immediately by the smallest negative number. Further, the largest negative number appears at the end of the range (at binary number $2^N$), and counting once more results in rollover since the number $2^N+1$ cannot be represented. Thus, 0 follows $2^N$ in the count range, so the largest negative number is immediately adjacent to the smallest positive number. Because of this, a simple operation like ‘2-3’, which requires counting backwards from two three times, will not yield the expected result of ‘-1’, but rather the largest negative number in the system. A better system would place the smallest positive and negative numbers immediately adjacent to one another in the count range, and this is precisely what the 2’s compliment representation does. The number wheels below illustrate signed-magnitude and 2’s compliment encodings for 8-bit numbers.

In 2’s compliment encoding, the MSB still functions as a sign bit it is always ‘1’ for a negative number, and ‘0’ for a positive number. The 2’s compliment code has a single ‘0’ value, defined by a bit pattern containing all 0’s (including the leading ‘0’). This leaves $2^N-1$ codes to represent all non-zero numbers, both positive and negative. Since $2^N-1$ is an odd number, we end up with $2^N/2$ negative numbers, and $2^N/2-1$ positive numbers (since ‘0’ uses one of the available codes for a positive number). In other words, we can represent one more non-zero negative number than positive, and the magnitude of the largest negative number is one greater than the magnitude of the largest positive number.

The disadvantage to 2’s compliment encoding is that negative numbers are not easily interpreted by humans (e.g., is it clear that ‘11110100’ represents a -12?). A simple algorithm exists for converting a positive number to a 2’s compliment-encoded negative number of the same magnitude, and for converting a 2’s compliment- encoded negative number to a positive number of the same magnitude. The algorithm, illustrated in Fig. 2 below, requires inverting all bits of the number to be converted, and then adding ‘1’ to the resulting bit pattern. The algorithm can be visualized in the 2’s compliment number wheel above by noting that inverting all bits reflects a number around an axis drawn through ‘0’ and the largest negative number, and adding one compensates for the 2’s compliment code containing one more negative code than positive code.

Important Ideas

• Digital circuits that perform arithmetic functions often must deal with negative numbers, so a method of representing negative numbers must be defined. An N-bit system can represent 2N total numbers, so a useful encoding would use half the available codes (i.e., $2^N/2$) to represent positive numbers, and half negative numbers.
• Signed magnitude representations simply designate the MSB as the sign bit, and the remaining bits as magnitude. In an 8-bit signed-magnitude system, ‘16’ would be represented as ‘00010000’, and ‘-16’ as ‘10010000’.
• In 2’s compliment encoding, the MSB still functions as a sign bit it is always ‘1’ for a negative number, and ‘0’ for a positive number. The 2’s compliment code has a single ‘0’ value, defined by a bit pattern containing all 0’s (including the leading ‘0’). This leaves $2^N-1$ codes to represent all non-zero numbers, both positive and negative.
• A simple algorithm exists for converting a positive number to a 2’s compliment-encoded negative number of the same magnitude, and for converting a 2’s compliment-encoded negative number to a positive number of the same magnitude.