# Binary Encoding of Integer

\[\mathbb{Z}\] contains positive and negative numbers, but nowdays
Computer system based on binary. There only have `0`

and `1`

can be
used. A simple solution is: **put signed symbol at the most significant
bit**. For example, use 8 bits can represent:

\[ -(2^7 - 1) = -127, -126, -125, … -0, +0, …, +125, +126, +(2^7 - 1) = +127 \]

This is an intuitive way. Therefore, early days computers applied it.

But this way(called **Sign magnitude**) has two big problems:

- waste a place: +0 and -0 are different in this system
- have to detect signed or not and use different ways to do an operation like addition

## 1. One's complement

To solve the second problem with the calculation complex, engineers
introduce **one's complement**. For example, a number: \[-43_{10}\] is
\[100101011_2\], the one's complement of it is \[111010100_2\](keep the
most significant bit and reverse the rest of bits). It still only works
for \[-127_{10} ... 127_{10}\] with 8 bits, didn't solve the first
problem obviously, why we say it solves the second one? Because we can
replace special digital electronics with two subtractions:

\[ 0010 - 0001 \equiv 0010 + (0011 - 0001) + (0001 - 0100) \]

Then we convert negative number to one's complement, and remember end-around carry(the bit over most significant bit should be add back), then get:

\[ 0010 + 0011 + 1110 + 0001 + 1011 \\ \to 0101 + 1110 + 0001 + 1011 \\ \to 10011 + 0001 + 1011 \\ \to 10100 + 1011 \\ \to 1[1111] \\ \to 1111 + 0001 \\ \to 1[0000] \\ \to 0000 + 0001 \\ \equiv 0001 \]

Or \[1110 + 0010\] would get \[1[0000] \to 0001\]

#### 1.0.1. Benefit

- no need to check signed bit
- reverse bits can use addition on subtraction

#### 1.0.2. Problem

- need a special unit for end-around carry
- there still have two zero representations

## 2. Two's complement

#### 2.0.1. Modular Arithmetic

If we have an integer use 3 bits to represent, then \[7 + 1 \equiv 0(mod \; 8)\] because of the overflow.

If we have k bits for an integer, then we can generalize to \[A + B \equiv C(mod \; 2^k)\].

#### 2.0.2. Abelian group

For additive, we have to implement an Abelian group: an **Identity**
element and every element has an **Inverse** element that adds them would
get the **Identity** element.

Now consider how can our 3-bits integer fit rules of Abelian group? If
`[000]`

represents `0`

, it's identity in our group. Assuming `[001]`

is
`1`

, how to know the representation of `-1`

? It's easy to get `[111]`

this answer because we know `[111] + [001] = 1[000]`

, overflow would be
dropped. And it cannot be any number except `-1`

, else we cannot find
others inverse element of `1`

. With this, we can keep finding an inverse
for `2=(`

[010]=) is `[110]`

and so on.

On the other hand, it still simple: `-1`

is the biggest negative number
in 3-bits encoding. Follows unsigned order, `[111] > [110]`

, then don't
need another way to compare numbers.

#### 2.0.3. Properties

Now we can see we map all possible combinations of bits to an exact number. Solve the first problem in previous solutions.

Even more, the subtractive of signed integer is additive of unsigned
number: `010 + 101`

can be `2 + 5`

or `2 + (-3)`

. Therefore:

\[ A + \neg A = 2^k - 1 \\ \to A + (\neg A + 1) = 2^k(mod \; 2^k) \\ \to -A := \neg A + 1 \]

Now we know we don't need subtractive, it can be replaced with one's complement plus one.

Back to group, one's complement would waste place about encoding is a
thing must happen, because in 3-bits encoding it maps `[111]`

and
`[000]`

. In two's complement the axis of symmetry pass through `[000]`

,
therefore, we won't get repetitive representations of zero.

Extend this `[001]`

maps to `[111]`

in two's complement, maps to `[110]`

in one's complement. Therefore, one's complement plus one would be two's
complement.