Two’s Complement or how computers do math.
Numbers in computer are stored as groupings of bits. The encoding between numerical values and bit patterns is chosen for convenience of the operation of the computer. Computers represent data in sets of binary digits. The representation is composed of bits, which in turn are grouped into larger sets such as bytes.
A bit is a binary digit that represents one of two states. The concept of a bit can be understood as a value of either 1 or 0, on or off, yes or no, true or false. (wikipedia)
While a single bit represents two values, a combination of bits represent larger values.
The amount of possible combinations doubles with each binary digit added. A byte is a bit string, that consists of bits and represents a character. On most computers it’s an 8 bit string.
Computers represent binary numbers in octal (base-8: numbers 0 through 7) and hexadecimal (base-16: 0 through 9 and A through F) format.
What is two’s complement?
Two’s complement is a mathematical operation on binary numbers, as well as a binary signed number representation (required to encode negative numbers in binary number system) based on this operation.
The two’s complement number behaves like the negative number of the original number.
Two’s complement = one’s complement + one.
Where one’s complement is the value obtained by inverting all the bits of the binary representation of the number.
example:
8 bits binary representation of number 9 (it’s absolute value): 0000 1001
getting it’s one’s complement by swapping zeros and ones: 1111 0110
getting two’s complement by adding one to one’s complement to get negative 9: 1111 0110 + 0000 0001 = 1111 0111
01111111
In two’s complement notation, a positive number is represented by it’s ordinary binary representation. A two’s complement 8-bit number can only represent positive integers from 0 to 127 (01111111), because the rest of the bit combinations with the most significant bit as ‘1’ represent the negative integers −1 to −128. Therefore, if the most left number of binary representation of a number is 1, it means that a negative number is presented.
Negative numbers are represented by the two’s complement of the absolute value.
How do we get the two’s complement of a binary number.
To complete this operation we need to invert or flip the bits and add the value of 1 to the result of this operation.
example:
The decimal number 5 in binary is:
0000 0101
To make this number negative we should flip zeros to ones and ones to zeros:
1111 1010
This number is the one’s complement of the decimal value -5. To get two’s complement one we need to turn it’s most significant bit (most right) to 1 by adding one (binary representation 0000 0001).
1111 1011
Now we got the negative value.
Why does this work?
Inverting and adding one is actually a pretty straightforward mathematical computation.
To get a negative number of a digit we simply need to subtract this digit from zero.
Same method works in binary. Before performing this operation, there are some facts to remember.
Binary subtraction facts:
- 0–0=0
- 1–0=1
- 1–1=0
- 10–1=1
The first three are the same as in decimal, but the forth one is the borrow case, when you need to subtract 1 from 0 and you are borrowing 1 from the next left position.
Binary addition facts:
- 0+0=0
- 1+0=1
- 1+1=10
- 10+1=11
When the result of the addition has 2 digits, write down the least significant one and carry the most significant one to next column.
Now let’s get a negative number of binary representation of 5 (8 bits). We will subtract 0000 0101 from 0000 0000 and add 1 to the most right.
Negative number of binary representation of 8:
That is how negative numbers are obtained.
However there is one exception — the most negative number. Since a positive value of 128 can’t be presented with an 8-bit signed binary number, the two’s complement of -128 in an 8-bit system results in the same binary number.
