uncategorized

Understanding Number Representation System

There is two well-known number representation in computer: one’s complement and two’s complement. While the latter one is widely adopted almost everywhere in the computer, the former one is still used in some fields, such as TCP/IP Protocol.

For convenience, we are all discussing a $k$-bits system.

One’s complement

One’s complement means that, for negative numbers, they are represented by the binary number of their absolute value with all the bits flipped. Note, the sign bit is also considered as flipped (as they are $1$ rather than $0$). The well-represented range of numbers are $[-2^{k-1}+1, 2^{k-1}-1]$.

Although “flip” is used almost everywhere, but there is a more intuitionistic understanding, if $n < 0$

$$
n = (2^k - 1) + n
$$

For difference of two arbitrary numbers $a - b$, take the situation $a > 0 \land b > 0$, we would obtain the following equation in one’s complement,

$$
s = a - b + (2^k - 1)
$$

If $a > b$, we would find that the number would exceed $2^k$, which is considered in one’s complement arithmetic: Any carry found in sum need “wrapping around”. Meanwhile, we can re-paraphrase the equation so that,

$$
s = (a - b - 1) + 2^k
$$

which indicates the carry is $1$ and adding 1 back we have $s = a - b$.

In another case, if $a - b < 0$, this immediately follows the definition.

Two’s complement

Most of the calculation we can follow from one’s complement system, while the well-represented range of numbers are $[-2^{k-1}, 2^{k-1}-1]$.

For expression $a - b$, in two’s complement system we would have

$$
s = a - b + 2^k
$$

If $a - b > 0$, 2^k is simply thrown away without any impacts on the correctness, and if $a - b < 0$ it is exactly the definition.

Comparison between two system

One’s complement system have an obvious disadvantage: $0$ has two representation. Think of the case that $(-1) + 1$, we would have

$$
s = 1 - 1 + 2^k - 1 = 2^k - 1
$$

If we follow the definition that negative numbers (it is a negative number as the sign bits is $1$) are flipped of its absolute value, we would obtain that $s$ has value $0$. Thus here we have two representation of $0$, which is quite unwanted.

Meanwhile, the arithmetic of one’s complement system needs to take care of the carry bit to keep it working. But the two’s complement system has no such worry.

As a result, one’s complement system is replaced by two’s complement.

Share