twos_complement.md

   1 # Two's Complement
   2
   3 Two's complement is an elegant way of encoding signed (i.e. potentially negative) integer (and possibly also [fixed point](fixed_point.md)) numbers in [binary](binary.md). It is one of the most basic concepts to know as a programmer; for its simplicity and nice properties two's complement is the way that's used to represent binary integers almost everywhere nowadays. Other ways of encoding singed numbers, mainly [sign-magnitude](sign_magnitude.md) and [one's complement](ones_complement.md), are basically always inferior.
   4
   5 Why is two's complement so great? Its most notable advantages are:
   6
   7 - **There is only one [zero](zero.md) value** (while other encodings such as sign-magnitude and one's complement have positive and negative zero which wastes values and complicates algorithms).
   8 - **Highest bit indicates the number sign** in the same way as e.g. in sign-magnitude and one's complement representations, i.e. determining whether a number is positive or negative is just as easy as in the more naive representations.
   9 - **Addition, subtraction and multiplication (both signed and unsigned!) work the same as with unsigned representation and overflow naturally**, i.e. we can have exactly the same hardware for these operations as for unsigned numbers and we don't even have to know whether the number is supposed to be unsigned or signed (this of course does NOT hold for any operation, e.g. division or comparison). Operations such as decrementing 0 or incrementing -1 correctly yield -1 and 0, respectively, without any special conditions. Subtraction can simply be done as adding a negated value. One's complement and sign-magnitude have to have special conditions for many of these situations.
  10 - **Positive values and zero are the same as the straightforward unsigned representation**, i.e. it is "backwards compatible" with the straightforward representation. For example the 4 bit value `0011` represents number 3 in two's complement just like it does in a normal unsigned binary number. (This also holds in sign-magnitude and one's complement.)
  11 - **Multiplying by -1 is still relatively simple** -- even though it is a tiny bit more expensive than in one's complement or sign-magnitude, it is still pretty straightforward (only requires two operations instead of one) and in [hardware](hardware.md) it can be implemented just as fast.
  12
  13 TODO: disadvantages?
  14
  15 *N* bit number in two's complement can represent numbers from *-(2^N) / 2* to *2^N / 2 - 1* (including both). For example with 8 bits we can represent numbers from -128 to 127.
  16
  17 **How does it work?** EZ: the highest (leftmost) bit represents the sign: 0 is positive (or zero), 1 is negative. To negate a number negate all its bits and add 1 to the result (with possible overflow). (There is one exception: negating the smallest possible negative number will give the same number as its positive value cannot be represented.)
  18
  19 In other words given *N* bits, the positive values representable by two's complement with this bit width are the same as in normal unsigned representation and any representable negative value *-x* corresponds to the value *2^N - x*.
  20
  21 **Example:** let's say we have a 4 bit number `0010` (2). It is positive because the leftmost bit is 0 and we know it represents 2 because positive numbers are the same as the straightforward representation. To get number -2, i.e. multiply our number by -1, we negate the number, which gives `1101`, and add 1, which gives `1110`. We see by the highest 1 bit that this number is negative, as we expected. As an exercise you may try to negate this number back and see we obtain the original number. Let's just now try adding 2; we expect that adding 2 to -2 will give 0. Sure enough, `1110` + `0010` = `0000`. Etcetc. :)
  22
  23 The following is a comparison of the different representations, notice the shining superiority of two's complement:
  24
  25 | value | unsigned | two's com. | sign-mag. | one's com. | biased |
  26 | ----- | -------- | ---------- | --------- | ---------- | ------ |
  27 |  000  | 0        | 0          | 0         | 0          | -4     |
  28 |  001  | 1        | 1          | 1         | 1          | -3     |
  29 |  010  | 2        | 2          | 2         | 2          | -2     |
  30 |  011  | 3        | 3          | 3         | 3          | -1     |
  31 |  100  | 4        | -4         | -0        | -3         | 0      |
  32 |  101  | 5        | -3         | -1        | -2         | 1      |
  33 |  110  | 6        | -2         | -2        | -1         | 2      |
  34 |  111  | 7        | -1         | -3        | -0         | 3      |