Two's Complement Signed Integers

by Paul Hornsey

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?

Basic Unsigned 3 bit Numbers

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?

Basic Signed Bit Numbers

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).

What Happened to One’s Complement?

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

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?

Adding and Subtracting

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.

Dealing with Overflow

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.

Overflow Flag

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.

Summary

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.

Paul Hornsey

Paul Hornsey

Paul Hornsey has developed software since 8 bit machines were cool. Since graduating from Heriot-Watt University in Computer Science he has worked for companies developing software from serious industrial code, to games and other cool stuff.

He is currently one part of 1partCarbon where the emphasis is on developers enjoying their life and career.