less_retarded_wiki

main page, file list (582), source, all in md+txt+html+pdf, report abuse, stats, random article, consoomer version

Two's Complement

Two's complement is an elegant way of encoding signed (i.e. potentially negative) integer (and possibly also fixed point) numbers in binary. 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 and one's complement, are basically always inferior.

Why is two's complement so great? Its most notable advantages are:

TODO: disadvantages?

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.

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.)

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.

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. :)

The following is a comparison of the different representations, notice the shining superiority of two's complement:

value unsigned two's com. sign-mag. one's com. biased
000 0 0 0 0 -4
001 1 1 1 1 -3
010 2 2 2 2 -2
011 3 3 3 3 -1
100 4 -4 -0 -3 0
101 5 -3 -1 -2 1
110 6 -2 -2 -1 2
111 7 -1 -3 -0 3

Powered by nothing. All content available under CC0 1.0 (public domain). Send comments and corrections to drummyfish at disroot dot org.