Negative Numbers in Hardware: Two's Complement

In the previous articles all our numbers were positive. In this one we deal with negative numbers. The constraint is simple to state: a CPU has only wires carrying HIGH or LOW. No wire has a minus sign on it, yet the CPU has to compute $5 - 7 = -2$ and get it right. Engineers tried a few schemes before settling on one, two’s complement, and the reason it won is that it makes the hardware simpler.

The problem

A 4-bit register holds exactly 16 bit patterns, 0000 to 1111. There is no extra slot for a sign. Whatever scheme we use for negative numbers has to fit inside those 16 patterns, so the only question is which patterns mean what.

Sign-magnitude

The obvious idea is to use the leftmost bit (the MSB) as a sign: 0 for positive, 1 for negative. The remaining bits hold the magnitude.

The range is −7 to +7. It is easy to read, but it has two problems that make it a poor fit for hardware.

First, there are two zeros, 0000 and 1000. That wastes a pattern and complicates every comparison, since “is this zero?” now has two answers to check.

Second, the arithmetic is messy. To add a positive and a negative number the hardware has to compare the signs, work out which magnitude is larger, subtract, and then set the sign of the result. You cannot use a plain adder; you need separate subtraction logic, which costs area and power.

Sign-magnitude does survive in one place: the sign of a floating-point number is stored this way. For integers it is rarely used.

One’s complement

The next idea is to represent $-N$ by inverting every bit of $+N$. Since +5 is 0101, −5 is 1010.

Addition is now cleaner. You add the bit patterns directly, with one extra rule: if a carry comes out of the leftmost bit, add it back into the rightmost bit. This is the end-around carry. Adding +3 and −3:

  0011  (+3)
+ 1100  (-3)
------
  1111  (-0 in one's complement)

It works, but there are still two zeros (0000 and 1111), and the end-around carry makes a fast adder awkward. Some early machines used one’s complement, the CDC 6600 among them, but the industry moved on.

Two’s complement

Two’s complement asks a different question: which bit pattern, added to $+N$, gives exactly zero?

In a 4-bit system everything wraps at $2^4 = 16$, so $-N$ is whatever you add to $N$ to reach 16. For $N = 5$:

$$16 - 5 = 11 = 1011_2$$

Invert and add one

You do not have to subtract from 16 each time. The mechanical shortcut is: invert all the bits, then add 1. Starting from +5, 0101:

• Invert: 1010
• Add 1: 1011

Check that it works

Add +5 and −5 with an ordinary binary adder:

  0101  (+5)
+ 1011  (-5)
------
 10000

We only have four bits, so the fifth bit is discarded and the result is 0000. Zero, as required.

This is the point of two’s complement. The adder does not need to know whether the numbers are signed. It adds bit patterns. Whether 0101 + 1011 means $5 + 11 = 16$ (unsigned, wrapped to 0) or $5 + (-5) = 0$ (signed) is a matter of interpretation in your code. The hardware is identical in both cases.

The number circle

Figure 1 shows the sixteen 4-bit patterns arranged on a circle. Going clockwise counts up: 0000, 0001, up to 0111, which is +7. One more step is 1000, and in two’s complement that is −8. Keep going and 1001 is −7, up to 1111, which is −1, and one more step wraps back to 0000.

With $n$ bits the range is

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

The range is not symmetric. Zero uses one of the “positive” patterns, so 8 bits can hold −128 but only +127. One consequence that catches people out: the absolute value of −128 cannot be represented in a signed 8-bit integer, and negating it gives you −128 back.

The three schemes side by side

All three agree on the positive values. Two’s complement has a single zero and one extra negative value, and, more importantly, it works with an unmodified adder.

In Verilog, nets and registers are unsigned unless you say otherwise. If you want the tool to treat a value as two’s complement, declare it signed:

reg signed [7:0] my_value;

Sign extension

Suppose you have the 8-bit signed value −75, which is 10110101, and you need it in a 16-bit register. Padding with zeros on the left gives 0000000010110101, which is +181. Wrong.

The correct operation is sign extension: copy the sign bit into all the new upper bits.

8-bit value:            1011 0101            (-75)
Sign-extended to 16:    1111 1111 1011 0101  (still -75)

A positive value (MSB 0) is padded with zeros, a negative one (MSB 1) with ones.

Verilog zero-extends by default when you assign a narrow value to a wide one. To get sign extension, both sides need to be declared signed, or you wrap the source in $signed(). Forgetting this is one of the most common arithmetic bugs in RTL, and it is silent: the simulation runs and the numbers are simply wrong.

Practice Exercise

1. Write −19 as an 8-bit two’s complement value.
2. What decimal value is the 8-bit two’s complement pattern 11100110?
3. Sign-extend 1010 (4-bit) to 8 bits.

Now that we can represent positive and negative integers, the next article does arithmetic with them: binary addition and subtraction, how overflow is detected, and a first look at fixed-point fractions.