Representing Negative Numbers

Back to Quick Hacks

This is an extract from an upcoming post on the implementation of Pong Wars for the Commodore 64, released early as it's a standalone digression from the main body of the post.

Computers were, to begin with, exclusively the domain of mathematicians and people who would be familiar with the esoteric field of binary numbers, so the number handling was built around being able to read those numbers off from the "blinkenlights" directly in binary. The simplest way to handle both positive and negative numbers was simply to mark one bit in the number as "the negative bit", and the rest of the number would represent the value; this was called "sign and magnitude" representation. For example:

Twenty-three and negative twenty-three:
0 0010111
1 0010111

To perform a subtraction (or to add a negative number, which is functionally equivalent) while only having adding circuitry, the computer needs to perform some precalculation otherwise it'll end up with the wrong answer:

  [63 - 23]      [63 + -23]
  00111111   =   00111111
- 00010111     + 10010111
                 --------
                 11001100
                 negative eighty six

The sign-and-magnitude negative number needs to be inverted (or one's-complemented in the mathematical jargon) when performing a subtraction, so that adding it has the intended effect of reducing the value instead of piling on top:

  [63 - 23]      [63 + -23]
  00111111   =   00111111
- 00010111     + 11101000
                 --------
              [1]00100111
                 thirty nine (and a carry)

Except complementing doesn't quite fix it: because sign-and-magnitude numbers can have zero (00000000) and negative zero (10000000), we need to add one after inverting to step over the negative zero value:

  [63 - 23]      [63 + -23]
  00111111   =   00111111
- 00010111     + 11101001
                 --------
              [1]00101000
                 forty (and a carry)

To summarise: negative numbers were represented as a negative sign bit and the value as the magnitude, for easier reading off from binary displays, but the computer would need to first invert the number and then add one in order to perform the addition of a negative number.

As binary read-off displays went away with the growing ubiquity of computing, it began to make sense to simplify the representation of negative numbers not for the human mathematician using the computer, but for the computer's internal operation. The best thing for the computer, of course, would be to remove this whole pipeline of needing to complement the number and add one, before being able to add a negative number.

And that's how we landed at two's-complement (two's because we add one to the one's-complement) representation as the standard for binary negative numbers: if the sign bit is set to negative in the number, the rest of the value is already inverted and has one added, so the computer just needs to add the whole value as normal.

This does increase the cognitive load on a programmer working at a low level, because your binary numbers no longer read "normally":

00000000 =    0
00000001 =    1
00000010 =    2
...
01111110 =  126
01111111 =  127
10000000 = -128 (not -0)
10000001 = -127 (not -1)
10000010 = -126 (not -2)
...
11111110 =   -2
11111111 =   -1

But when are we going to be working at a sufficiently low level that we have to remember about two's-complement representation in the microcomputer age of the '80s, with high-level languages such as BASIC widely available? When we need to eke out more performance than BASIC can give us.

Display mode