2's Complement
Copyright: Tony Drewry
See also Binary etc.

Subtraction using complements

It is a curious fact that a computer subtracts using addition.
First a method  known as 2's Complement is used to create a negative representation of the number to be subtracted..
Then subtraction is a matter of adding the negative number to the number from which it is being subtracted. (!)
But before we look at 2's complement, let's use a familiar number system to understand the concept of complements.

Complements

The complement of a number is the number which when added to the original will make it equal to a  multiple of the base  number system.


The complement of a number can be used as a representation of that number as a negative - moreover, as a positive number representing a negative! It is really a bit of a trick which we can use to make subtraction easier for machines.
For example in the  decimal (base 10) system
the complement of 7 is 3  (i.e 7 + 3 = 10)
the complement of 8 is 2
etc.
the complement of 99 is 01 (i.e 99 + 1 = 100)
the complement of 78 is 22 (not 32)
the complement of 2000 is 8000
etc.

 Consider that:
-1 =  +9 -10  
-99 =
 +1 -100
-7 =  +3 -10  
-78 =
 +22 -100
-56 =  +44 -100   -200 = +800 -1000


If we can 'lose' the multiple of 10 which has been used to create the complement, then we can subtract using addition - based on the principle that :
subtraction is mathematically the same as adding the negative of the number we want to take away.


The complement method of subtraction uses  the complement  as a negative representation of the number to be subtracted.
For example  in the  decimal (base 10) system:


7 minus 3 is mathematically the same as 7 plus (minus 3)
i.e:  7 - 3 = 4 is  the same as 7 + (-3) = 4
3 minus 3 is mathematically the same as 3 plus (minus 3)
i.e:  3 - 3 = 0 is  the same as 3 + (-3) = 0
the complement of 3 is 7

7 minus 3  is  the same as 7 plus the complement of 3
so: 7 - 3 becomes 7 + 7  which = 14
If we remove the left-most 'additional' digit,
7 - 3 = 4  is the same as  7 + 7 = (1)4
We  discard additional left-most digits.
We can see them as being additional because  conceptually a new left-most column is added. 
In the above example '7 minus 3' is a single column subtraction and the answer will only require a single column.
Consider that if we are using a machine with cogs, or a computer with a fixed number of bits, it is easy to 'lose' the leftmost digit. In the following examples, all the results when we use a complement for subtraction have an additional 1 in the leftmost column - which we discard when looking at the answer. Note however that the '1's  also flag the result is a positive number.
 
1)
 7
-7
 0		 1a)
  7
 +3
1 0		 !
!
!		 2)
 99
-78
 21		 2a)
  99
 +22
1 21		 !
!
!		 3)
 2000
-1999
 0001		 3a)
  2000
 +8001
1 0001		 !
!
!		 4)
100
- 7
 93		 4a)
100
+ 3
103		 !
!
!		 5)
 100
-007
 093		 5a)
  100
 +993
1 093

In example 4a, the answer is incorrect! but   as soon as we realise that in this system: the number we are subtracting must have the same number of digits as the number from which we are subtracting, then we can obtain a correct result. Study the examples 5) and 5a) above. Can you see why the complement of 007 is 993?

In the following examples, note that there is no 'discard' column - I have put a '0' to denote this.
Can you see why the answers appear incorrect? and what needs to be done?

6)
 1
-2
-1		 6a)
  1
 +8
0 9		 !
!
!		 7)
  7
-17
-10		 7a)
  07
 +83
0 90		 !
!
!		 8)
 11
-78
-67		 8a)
  11
 +22
0 33		 !
!
!		 9)
 2000
-2999
- 999		 9a)
  2000
 +7001
0 9001

All the results in the sums above should be negative. The results in the sums using complements are negative but are still shown as complements (i.e as positive representations of negative numbers). If we were using a machine to do these calculations we could set it to note that there is no discarded leftmost digit and that in order to return a 'true' negative number, the result needs to be replaced by its complement with a minus sign in front.
So, in the examples above, '9' is the complement form of '-1', '33' = '-67', etc.

2's Complement and binary
 
Calculating the complement of a binary number

1.  Reverse the value of the bits in the binary number; i.e. change all the 0 bits to 1 and change 1s to 0. 
2.  Add 1 to the result. 

(This is a shortcut - alternatively, you can look at the string of bits and work out the complement as the binary number you would need to add to obtain the next whole multiple of 2) 
The above shortcut is known as '2's complement'.

Note that in '2's complement' notation  Positive numbers always start with '0' and Negative numbers with '1'

Getting 2's Complement - examples

Step 1 Step 2
+1 = 00000001
 00000001
becomes
11111110		  11111110
+00000001
 11111111		 -1 = 11111111
+12 = 00001100
 00001100
becomes
11110011		  11110011
+00000001
 11110100		 -12 = 11110100
+13 = 00001101
 00001101
becomes
11110010		  11110010
+00000001
 11110011		 -13 = 11110011
+87 = 01010111
 01010111
becomes
10101000		  10101000
+00000001
 10101001		 -87 = 10101001
+100 = 01100100
 01100100
becomes
10011011		  10011011
+00000001
 10011100		 -100 = 10011100

You can use the above numbers to check out that adding negative binary numbers (i.e. complements) to positive binary numbers works as subtraction. 

For example, the decimal sum '1 - 1', in binary representation:
(+1)   00000001
(-1)  +11111111
answer   100000000

Note that: the additional lefthand  bit flags whether the answer is positive (1) or negative (0) - as in the 'base 10' examples earlier.

Some examples of subtraction in binary using 2's complement

a)
12
-2
10
  01100
 +11110
1 01010		 not
  1100
 +1110
1 1010		 !
!
!		 b)
 87
-13
 74
  01010111
 +11110011
1 01001010		 !
!
!		 c)
  1
-13
-12
  00001
 +10011
0 10100		 not
  0001
 +0011
0 0100		 !
!
!		 d)
  87
-100
- 13
  01010111
 +10011100
0 11110011
(A bit like magic!)

Tony Drewry,  September 2002
Tony's Home Page