Binary Math Lesson 1:
Two's Complement Math
Signed Numbers
So far when we have discussed binary numbers we have only dealt with positive numbers, but it is important to have a way to represent negative binary numbers as well. Humans use a signed-magnitude system when dealing with decimal numbers by adding a + or - in front of a number to indicate whether it is positive or negative.
The most common method used for storing signed numbers on computers is the two's complement system. Two's complement numbers store the sign as the first bit so a number with a 1 in front is negative while a leading 0 indicates a positive number. You can always find the opposite of a two's complement number by finding its complement, or opposite value, and adding 1. You should also drop the first bit if it extends past the number of bits used in the system. So if you ended up with a 9-bit number in an 8-bit system you would drop the first digit. Below are some examples of binary numbers in two's complement form:
| Decimal | Two's Complement Binary |
|---|---|
| 127 | 01111111 |
| 126 | 01111110 |
| 2 | 00000010 |
| 1 | 00000001 |
| 0 | 00000000 |
| -1 | 11111111 |
| -2 | 11111110 |
| -127 | 10000001 |
| -128 | 10000000 |
To understand how two's complement works look below to see how we converted from the positive numbers to the negative numbers. The ' sign means we are taking the complement of a number.
011111111' = 100000000
100000000 + 1 = 100000001
(-127)
00000010' = 11111101
11111101 + 1 = 11111110 (-2)
00000001' = 11111110
11111110 + 1 = 11111111 (-1)
Now look what happens when we try to convert 0 and -128 assuming we are using an 8-bit system.
00000000' = 11111111
11111111 + 1 = 100000000 = 00000000
100000000' = 011111111
011111111 + 1 = 100000000
The reason the two above cases gave us the same result has to do with how two's complement form works. In two's complement there are more negative numbers than positive numbers so you cannot find the complement of the smallest negative number. This means the range of numbers in an n-bit two's complement system is -2n-1 to 2n-1- 1. One of the benefits of two's complement is that it only has one way to represent 0. Some signed number system have both a positive 0 and a negative 0. When you try to find the complement of 0 it results in an overflow so the final result gives you 0 again.
The main benefit of a two's complement system is how easy it makes addition, subtraction, and other mathematical operations. This is the reason why it is used for most computer systems.
Two's Complement Addition
Addition in two's complement form is fairly simple. You simply add all the bits together as you would in decimal form and ignore any carry out. Below are some examples.
11
0111 (7)
+1100 (-4)
10011 (3)
11
1101 (-3)
+1110 (-2)
11011 (-5)
111
0111 (7)
+0001 (1)
1000 (-8)
The final calculation above is incorrect because adding 1 to 7 in a 4-bit system would result in an overflow so the sign-bit is changed incorrectly. This is why you will see integer values suddenly become negative when you go past the integer maximum in Java instead of crashing your program.
Two's Complement Multiplication
Multiplication in binary works just like it does in decimal. You start by multiplying the multiplicand (the top number) by the first digit on the right of the multiplier (the bottom number). Doing this will result in a partial product. Every time you move to a new digit of the multiplier you shift the partial product to the left. The sum of all the partial products will be the final product. Look at the following example to see how this is done:
1101 Multiplicand
x 0110 Multiplier
0000 Partial
1101 Products
1101
+ 0000
1001110 Product
Multiplication in binary is even easier than it is in decimal because the partial products can only have two possible values, one of which is just zeroes the other of which is the multiplicand. Below are some multiplication examples using two's complement numbers.
1101 (-3)
x 1111 (-1)
1101
1101
1101
1101
11000011 (3)
0011 (3)
x 0010 (2)
0000
0011
0000
0000
0000110 (6)
1100 (-4)
x 0010 (2)
0000
1100
0000
0000
0011000 (-8)
0101 (5)
x 0010 (2)
0000
0101
0000
0000
0001010 (-2)
Multiplication generally results in overflow so you need to remove the leading bits to get the result. The final result, however, goes past the maximum value for 4-bit binary numbers (0111) so it results in an incorrect solution.
Hopefully you also noticed the pattern when you multiply a binary number by two (10). All you have to do is take the other number and shift all its bits to the left and add a trailing zero. Binary division by two works the opposite way. In division by two you shift all the bits to the right and add a zero to the front.