Two's complement

From Sonic Retro

Two's complement is by far the most common method of representing signed numbers (those that can be either negative or positive) in computing. Virtually every processor made since the late 1970s uses it, including the Z80 and 68000.

Two's complement is calculated by taking the bitwise NOT of a number (or complementing it) and adding one to the result. Any carry (overflow) bits are ignored. For instance, to find -7, we would start with the eight-bit binary number 0000 0111:

```!(0000 0111) = 1111 1000
1111 1000 + 1 = 1111 1001
```

The process is reversable:

```!(1111 1001) = 0000 0110
0000 0110 + 1 = 0000 0111
```

Let's say we wanted to find the two's complement of 0.

```!(0000 0000) = 1111 1111
1111 1111 + 1 = 1 0000 0000 = 0000 0000
```

The two's complement of 0 is 0. A negative zero is impossible when using two's complement.

It should be noted that when the number is positive, the most significant bit will be clear (zero). If it's negative, the MSB will be set (one). The MSB is often referred to as the "sign bit" for this reason. "Sign extention" is the process of extending an 8-bit number into a 16-bit number, or a 16-bit number into a 32-bit number, by repeating the original number's sign bit in all of its more significant bits. For instance, our 8-bit 7 can be made into a 16-bit 7:

```0000 0111 = 0000 0000 0000 0111
```

Likewise for -7:

```1111 1001 = 1111 1111 1111 1001
```

In both cases, the number in bit 7 was repeated in bits 8-15.

It is very simple and cheap to implement signed addition when using two's complement, because you do not need to determine the sign beforehand. For example, let's take 5 + -3:

```  0101
+ 1101
------
10010 = 0010
```

The intermediate result is 18, which seems incorrect. But dropping the overflow bit gives us the correct answer of 2. This works for any set of numbers. Note that 5 + (-3) is the same as 5 - 3. It follows that we can use an adder circuit to subtract numbers by taking the two's complement of the subtrahend if the numbers have the same sign.