NSI Rocks !

Two's Complement

Representing negative numbers in binary

In binary, we naturally represent positive numbers. But how do we represent negative numbers?

The most widespread solution is two's complement.

Two's complement allows using the same circuits to perform additions and subtractions, whether the numbers are positive or negative.

Principle

We choose a fixed size in bits (often 8, 16, 32 or 64 bits). The leftmost bit is called the sign bit:

  • 0 means the number is positive
  • 1 means the number is negative

Two's complement allows encoding integers from −2n−1-2^{n-1} to 2n−1−12^{n-1}-1 for nn bits.

For example, on 8 bits:

  • min: −27=−128-2^7 = -128
  • max: 27−1=1272^7 - 1 = 127

Calculating two's complement

To encode a negative number −x-x on nn bits:

  1. We encode xx in binary (positive) on nn bits
  2. We invert all bits (one's complement)
  3. We add 1 to the result
Two's complement of xx (on 8 bits):
  • x=5x = 5: 00000101
  • Inversion: 11111010
  • +1: 11111011 ➜ this is the representation of -5!

Why does it work?

Because we get consistent behavior with binary addition:

TODO

Warning in Python!

In Python, integers are not limited to 8 bits. Thus:

~255 = -256

This can cause errors if we expect an 8-bit result.

To simulate an 8-bit operation in Python:
(~x) & 255
This keeps only the 8 rightmost bits (like a byte).

Two's complement and bounds

On 8 bits, possible values are:

BinaryDecimal
000000000
000000011
01111111127
11111111-1
11111110-2
10000000-128
In two's complement on 8 bits, there are as many negative numbers as positive ones - except there's one more negative.

En complément à deux sur 8 bits, il y a autant de nombres négatifs que positifs - sauf qu'il y a un négatif de plus. ::