Two's Complement
Jun 25th, 2021 - written by Kimserey with .
Last week we looked at bitwise operators in Python. We briefly went through all of them without looking into how signed intergers were represented. In this post we will be looking at Two’s complement, Python’s way of storing signed integers, and finally answer the question of why ~9 = -10.
Two’s Complement
The Two’s complement is an operation on binary numbers used to represent signed integers. Used over a byte, we can encode signed integers from -128 to 127, with the last bit indicating the sign of the integer but also being used to store value.
The way to compute the Two’s complement is by taking the One’s complement and adding 1.
For example if we want to encode -12, we can look at 12 and compute the Two’s component which would encode the inverse -12:
1
2
3
0000 1100 (12)
1111 0011 (-12 One's complement)
1111 1100 (-12 Two's complement)
1111 1100 would then be -12 in Two’s complement.
The advantage over One’s complement is that there isn’t a duplicate representation of 0 with 0000 0000 and 1111 1111, hence allowing one more value to be represented -128.
| Decimal value | Two’s-complement |
|---|---|
| 0 | 0000 0000 |
| 1 | 0000 0001 |
| 2 | 0000 0010 |
| 126 | 0111 1110 |
| 127 | 0111 1111 |
| −128 | 1000 0000 |
| −127 | 1000 0001 |
| −126 | 1000 0010 |
| −2 | 1111 1110 |
| −1 | 1111 1111 |
We can see that positive values are just represented the same way as regular binary (except up to 127), and negative values all have their most significant bit as 1.
Python Complement
In Python, we can get the complement of a binary value with ~. But when we first look at it, it may look strange:
1
2
3
4
5
6
7
8
>>> bin(9)
'0b1001'
>>> ~9
-10
>>> bin(~9)
'-0b1010'
The complement of 9 is -10. The reason why is that -10 is actually the Two’s complement representation of NOT(0000 1001), which is the complement of 9.
If we compute the complement of 9 we have:
1
2
0000 1001 (9)
1111 0110 (~9)
And separately, if we find -10 we will have:
1
2
3
0000 1010 (10)
1111 0101 (-10 One's complement)
1111 0110 (-10 Two's complement)
So we can see that ~9 = -10 as negative value are encoded in Two’s complement in Python.