- Software, Computer Science, Performance

Have you ever wondered why integer ranges have a larger negative than positive range? In Java, for example, ‘int’ types are 32 bits with a range of:

–2,147,483,648 to 2,147,483,647

So why the extra one on the negative range and not the positive? The answer is that most modern processors like integers to be in a format known as 2’s Complement Signed Integers. So what is this and why are they used?

The easiest numbers to represent in binary are positive unsigned integers. We can just directly convert the base 2 binary value back to decimal. We’ll keep it simple and just use three bits per number:

Binary | Decimal |
---|---|

000 | 0 |

001 | 1 |

010 | 2 |

011 | 3 |

100 | 4 |

101 | 5 |

110 | 6 |

111 | 7 |

So how might we represent negative values?

Lets make the leftmost bit flag if the number is positive or negative. ‘0’ for positive, ‘1’ for negative:

Binary | Decimal |
---|---|

000 | 0 |

001 | 1 |

010 | 2 |

011 | 3 |

100 | –0 |

101 | –1 |

110 | –2 |

111 | –3 |

This looks usable but has a few features which look strange. The first weirdness is that we have a negative zero (–0).

Another method for storing signed integers is to flip all the bits if the value is to be negative, else leave it positive. This is called one’s complement and looks as follows:

Binary | Decimal |
---|---|

000 | 0 |

001 | 1 |

010 | 2 |

011 | 3 |

100 | –3 |

101 | –2 |

110 | –1 |

111 | –0 |

Notice that it still has the double zero problem.

Two’s complement solves this double zero problem and provides some bonus features. To negate a number in 2’s complement, you first flip the bits then add one.

For Example, –2 is found as follows:

- 010 = Positive 2
- 101 = Flipped bits
- 110 = One added

The results with our 3 bit example is as follows:

Binary | Decimal |
---|---|

000 | 0 |

001 | 1 |

010 | 2 |

011 | 3 |

100 | –4 |

101 | –3 |

110 | –2 |

111 | –1 |

Now we only have one zero and an extra negative number. Our range of representable integers is now –4 to 3. So this answers why the extra negative range, but why is two’s complement used so much?

The real advantage of 2’s Complement representation is that it makes addition and subtraction an easy task for the processor. To subtract a number, you just add the negative binary representation.

3 - 2 becomes 3 + (–2)

```
011
+ 110
---
001
```

11

(For later, note that we carried a bit into and out of the most significant bit MSB) We just ignore the extra carried bit, so the result is 001 = 1 decimal which is correct.

When adding or subtracting bit limited numbers, there is always the chance that the result would need extra bits to represent it. For example: 3 + 3

```
011 (3)
+ 011 (3)
---
110 (-2)
11
(Note: has a carry into the MSB but not out of it)
```

Looking up our 2’s complement table, we see that 110 is decimal –2.

So something has gone wrong! Lets try a negative example:–4 + –4

```
100
+ 100
---
000
```

1

(Note: here we only carry a bit out of the MSB bit)

Again, –8 would need an extra bit, so the result is rubbish (0). What is needed is a way to detect when a problem has occurred so our programs don’t produce rubbish output. This is where some of the processor flags come to our rescue.

The 80x86 processor provides a flag named Overflow (OF). For our proposes we can think of this flag getting set to ‘1’ if the result of an addition would result in a two’s complement error. To actually see how the overflow is set, we need to look at two things. One, was there a carry into the left-most bit (MSB), and two, was there a carry out of that last bit. The second of these is recorded in another flag called the Carry Flag (CF).

The following table shows the combinations of carries which signal an overflow:

Carry into MSB | Carry out | Overflow |
---|---|---|

false | false | false |

false | true | true |

true | false | true |

true | true | false |

Overflow is needed to chain bytes together in order to sum much larger numbers. This is needed if the numbers are larger than the processor’s maths brain (ALU) can handle.

So there you have it. Two’s complement numbers are for storing signed integers which makes it really easy and fast for a processor to add and subtract.