Two's Complement

This guide explains how negative integers are stored using Two's Complement and how arithmetic is performed using negative integers.

Representing negative integers using Two's Complement

The largest unsigned integer that can be stored in N bits can be expressed as (2N )-1. For example, 4 bits can represent integers from 0 to (24)-1, or in other words 0 to 15. So a 4 bit unsigned integer can store any of the following values:

NOTE: The diagram is not a representation of memory or bits, it's just range of integers.

In an unsigned integer all available bits are used to represent positive integers.
But for signed integers, only half the available bits are used to represent positive integers. The other half are used to represent negative integers. So a 4 bit signed integer can store any of the following values:

Unsigned integers 0 to 15 can be stored in 4 bits.
Signed integers -8 to 7 can be stored in 4 bits.

Two's Complement is a representation of negative integers using positive integers. To calcuate the Two's Complement of a negative integer, -x, in an N bit integer, do (2N)+(-x). Remember that addition of a negative number is subtraction. For example, to calculate the Two's Complement of -4 in an 8 bit integer do (2 8 )+(-4) = 12. From this we see the Two's Complement of -4 is 12. This is sumarised in the following two diagrams:

Unsigned integer range:
Signed integer range:

Looking at the following two tables we see a problem that the hex and binary for signed and unsiged integers is the same:

Decimal 2's Complement Binary Hex Note
-4 12 1100 0xC
-3 13 1101 0xD
-2 14 1110 0xE
-1 15 1111 0xF
Decimal 2's Complement Binary Hex Note
12 N/A 1100 0xC
13 N/A 1101 0xD
14 N/A 1110 0xE
15 N/A 1111 0xF

The representation of -4 in a signed integer is the same as 12 in an unsigned integer. The representation of -6 in a signed integer is the same as 10 in an unsigned integer, and so on.

For this guide, assume the data type int is implemented using 4 bits on your computer and look at the following C++ code:

unsigned int x = 12; // x is 12
signed int x = 12; // x is -4

This is why it's important to understand implementation of data types when programming. Again, use the integer ranges to check this:

From this, two things become clear:

  1. To correctly interpret the integer 12 (for example), you must know whether it's the Two's Complement of a negative integer, or whether is really is representing the integer 12.
  2. Signed and unsigned integers have identical ranges, but store different values within the range.

If you want to try this for yourself, you can create a C++ console application similar to:

int main(int argc, char *argv[])
{
    // Store the maximum allowed value on a 32 bit system in unsigned int and signed int data types.
    
    unsigned int a = 4294967295;      // (2^32)-1
    signed int b = 4294967295;      // (2^32)-1
    
    cout << a << "\n";
    cout << b;
}

You will see that 'a' has the value 4294967295, but 'b' has the value -1

Addition and subtraction

Representing negative integers in binary is important because subtraction is performed through addition of negative integers. We will look at three examples:

5-2 is the same as 5+(-2). The Two's Complement integers we need are:

Decimal 2's Complement Binary Hex
5 5 0101 0x5
-2 14 1110 0xE

So to do 5+(-2) we actually do 5+14 = 19. This appears to be incorrect for two reasons:

  1. 5-2 does not equal 19
  2. We cannot represent the number 19 in a 4 bit integer...signed or unsigned
However the number 19 in binary is 10011. Note that it takes 5 bits to represent the integer 19 in binary, but the result will be stored in a 4 bit int. The most significant bit (10011) is lost through overflow and the actual result is 0011, which is 3. This is correct since 5-2=3

Lets do 2-5, which is equivalent to 2+(-5). The Two's Complement integers we need are:

Decimal 2's Complement Binary Hex
2 2 0010 0x2
-5 11 1011 0xB

So to do 2+(-5) we actually do 2+11 = 13. Again this appears incorrect. However looking at the following diagram we see that -3 is stored as 13 in Two's Complement form.

Unsigned:
Signed:

Since 13 can be represented in a 4 bit integer, we do not lose any bits through overflow.

Finally lets look at -2-2. It's equivalent is -2+(-2). The Two's Complement integers we need are:

Decimal 2's Complement Binary Hex
-2 14 1110 0xE

So to do -2+(-2) we actually do 14+14 = 28. In binary 28 is 11100. However we only have room for 4 bits so lose the most significant bit (11100) through overflow, the integer becomes 1100, which is 12 in decimal. It should be obvious by now that 12 is the Two's Complement of -4. Since -2-2 is -4, we have the correct answer.

Bitwise operators

Addition and subtraction can be achieved using the bitwise operators NOT and INC (complement and increment). For example to find the representation of -4, start with +4 in binary, then 'NOT' each bit, and finally INCrement the whole number:

Operator Binary Decimal
0100 4
NOT 1011 11
INC 1100 12

This is correct since -4 is stored as 12 in Two's Complement form. This is how the Arithmetic and Logic Unit (ALU) can perform addition and subtraction of negative integers using only NOT and INC.

Two's Complement calculator

-

Contact the author

Any bugs, improvements or comments, please contact jackwootton@gmail.com.