# 淺談計算機編碼(整數篇)
###### tags: basic

> 計算機中對於數字不管是十進位、二進位、十六進位、整數、浮點數等等的表達方式或運算操作，因為計算機本身的限制，都會跟人類世界直覺想像的有點不同，常常會因為某些觀念上的不齊全，直接用我們直覺的方式去撰寫就會有些無法預期的漏洞，所以熟悉跟將這些編碼化為自己的習慣是相當重要的。
>
> 這篇的撰寫是根據 CS:APP 這本書的第二章作為基礎，算是作為自己讀後彙整的筆記，並會搭配些許實驗。

## 實驗環境

$ uname -a
Linux noah-UX330UA 4.15.0-43-generic #46~16.04.1-Ubuntu SMP Fri Dec 7 13:31:08 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
$ gcc -version
gcc (Ubuntu 5.5.0-12ubuntu1~16.04) 5.5.0 20171010

### 16 進位表示
在計算機中最小的位址紀錄單元為 8 個 byte，而如果用二進位表示會太長，用十進位轉換成二進位又會太麻煩，所以都是用十六位元來表示位址。
在 C 語言中用 `0xFFFFFFFF` 的格式來表示記憶體位置，並且可以用`printf("%p", 變數);` 來印出記憶體表示之格式。
以下是三種進位的轉換表。

| 十六進位 |0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
| ------- | - | - | - | - | - | - | - | - | -
| 十進位 | 0 | 1| 2 | 3 | 4| 5 | 6 | 7 | 8
| 二進位 | 0000| 0001| 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000

| 十六進位 |9 | A | B | C | D | E | F |
| ------- | - | - | - | - | - | - | - |
| 十進位 | 9 | 10| 11 | 12 | 13| 14 | 15 |
| 二進位 | 1001| 1010| 1011 | 1100 | 1101 | 1110 | 1111

### byte 表示順序
byte 的表示順序根據計算機的不同分成兩種 `little endian` 和 `big endian` (大部分的機器都是以 `little endian` 作為表示，而網路傳輸使用的都是 `big endian`)。
* `little endian`
在 `little endian` 中，記憶體位置最低位數(最右)會放在記憶體的前面，例如 `0x01234567`。

| 0x100 | 0x101 | 0x102 | 0x103 |
| -------- | -------- | -------- |----
| 67 | 45 | 23 | 01 |

* `big endian`
在 `big endian` 中，跟 `little endian` 相反，最高位數放在記憶體最前面。

| 0x100 | 0x101 | 0x102 | 0x103 |
| -------- | -------- | -------- |----
| 01 | 23 | 45 | 67 |

* [Big-Endian 與Little-Endian 的差異與判斷程式碼- G. T. Wang](https://blog.gtwang.org/programming/difference-between-big-endian-and-little-endian-implementation-in-c/) 可以利用這個連結給的小程式來判斷自己電腦的表示式是哪種。

## 整數類型
在 C 語言中有許多不同的整數的類型，而這些類型在不同 bits 的機器上會有不一樣的最大值與最小值，下面的列表是在 32 位元跟 64 位元機器上值的範圍。

#### 32位元
| 整數類型 | 最小值 | 最大值 |
| ------------- | -------- | ------------ |
| [signed] char | -128 | 127 |
| unsigned char | 0 | 255 |
| short | -32768 | 32767 |
| unsigned short | 0 | 65535 |
| int | -2147483648 | 2147483647 |
| unsigned | 0 | 4294967295 |
| long | -2147483648 | 2147483647 |
| unsigned long | 0 | 4294967295 |
| int32_t | -2147483648 | 2147483647 |
| uint32_t | 0 | 4294967295 |
| int64_t | -9223372036854775808 | 9223372036854775807|
| uint64_t | 0 | 18446744073709551615 |

#### 64位元
| 整數類型 | 最小值 | 最大值 |
| ------------- | -------- | ------------ |
| [signed] char | -128 | 127 |
| unsigned char | 0 | 255 |
| short | -32768 | 32767 |
| unsigned short | 0 | 65535 |
| int | -2147483648 | 2147483647 |
| unsigned | 0 | 4294967295 |
| long |-9223372036854775808 | 9223372036854775807 |
| unsigned long | 0 | 18446744073709551615 |
| int32_t | -2147483648 | 2147483647 |
| uint32_t | 0 | 4294967295 |
| int64_t | -9223372036854775808 | 9223372036854775807|
| uint64_t | 0 | 18446744073709551615 |

## 整數表示
整數在計算中有兩種表示方式，一種是只能表示非負數，另外一種是能夠表示負數、零、正數，這兩種表示方式在編碼上都有些不同，其在不同位元的機器上也有不同，接下來就來介紹這兩種整數的編碼方法。

#### 無符號整數二進位編碼
$B2U_w(x) = \displaystyle\sum_{i=0}^{w-1}x_i2^i$
上面的公式是作為將二進位轉成無符號整數的公式。

$B2U_w([1011]) = 1 *2^3 + 0 * 2^2 + 1 * 2^1 + 1 *2^0 = 11$

#### 補數編碼(有符號整數表示法 two's complement)
利用二進位數中的最高位數來表示，如果是 `1` 就為負，`0` 則為正
$B2U_w(x) = -x_{w-1}2^{w-1}+\displaystyle\sum_{i=0}^{w-2}x_i2^i$
$B2U_w([1011]) = -1 *2^3 + 0 * 2^2 + 1 * 2^1 + 1 *2^0 = -8$

$B2U_w([0111]) = 0 *2^3 + 1 * 2^2 + 1 * 2^1 + 1 *2^0 = 7$

## 有號整數與無號整數之間轉換
> 所謂的有號和無號的轉換並不是在一般數學所表示的將 `-` 去掉就轉換成功，這兩個在編碼上就完全不同，無號是用二進位，有號是用 two's complement ，所能表示數字的範圍大小也不同，所以再做 `int -> unsigned` 或 `unsigned -> int` 時必須要意識到自己在幹麻，還有結果是否會是自己預期。

* **有號整數 -> 無號整數 轉換原理**

* 當要從有號整數轉成無號整數時，如果有號整數大於零的時候，就直接轉換成無號整數。

* 如果為負數要轉換為無號整數時，$x + 2^w$ 利用這個公式來計算，$w$ 為數據類型 bits 長。
* 例如在 16 bits 的機器上，要將 $-12345$ 轉換成無號整數，套用上述公式... $-12345 + 2^{16} = 53191$
* 特別注意到因為這樣轉換的方法，將 -1 轉換成無號整數後會變成在該機器上的無號整數最大值... $-1 + 2^{16} = 65535$

* **無號整數 -> 有號整數 轉換原理**
* 如果欲轉換的無號整數是小於有號整數的最大值(`參照整數類型的表格`)，就直接轉換。

* 如果是大於有號整數的最大值，套用 $x-2^w$ 的公式，$x$ 為無號整數，$w$ 為機器的 bits 數。
* 例如在 16 bits 的機器上， 給一數 $32768$ 為有號整數最大值再加一，套用公式就為 $32768 - 2^{16} = -32768$ ，這樣轉換下來就會得到有號整數的最小值。

* 如果是給無號整數的最大值 $65535$ 代入公式，$65535 - 2^{16} = -1$ 跟 *有號整數 -> 無號整數* 成對射。


這張圖能清楚的表示兩種表示方式的轉換。

## 整數運算
#### 無號整數加法
* 在加法的部份，因為類型能夠表達的數字大小有其範圍，如果兩者相加的數超過其範圍，多出來的部份就會在從 0 開始向上加。

#include <stdio.h>
#define UN_MAX = 4294967295
int main()
{
      unsigned number_one = UN_MAX;
	unsigned number_two = 2;
	unsigned sum = number_one + number_two;
	printf("%u\n", sum);
	return 0;
}

* 用上面簡單的程式來做個範例，宣告 `unsigned` 變數，而 `unsigned` 的最大值為 $4294967295$，將 `number_one` 宣告為最大值，再加 $2$，得到結果並不是預期的 $4294967297$，結果是 $1$，這代表此結果產生 `overflow`


* 上圖是以 4 位元的無符號整數作為範例，在 4 位元的數其最大值為 15 ， z 軸為平面 x 軸與 y 軸的總和，可以發現在當其兩軸總和超過 15 時就會從 0 開始繞回去往上加。

#### 有號整數加法
* 有號整數的 `overflow` 會有兩種，超出正值範圍的 `overflow` 或超出負值範圍 `overflow`

* 如果 $x+y \geq 2^{w-1}$，其得到的結果就會是 $x+y-2^w$ ($2^{w-1}$ 是此類型最大值範圍)，這樣為 `Positive overflow`。

* 如果 $x + y \leq -2^{w-1}$，其得到的結果就會是 $x+y+2^w$ ($-2^{w-1}$ 是此類型最小值範圍)，這樣為 `negative overflow`

* 實驗

#include <stdio.h>

#define INT_MAX 2147483647
#define INT_MIN -2147483648

int main()
{
      int number_one = INT_MAX;
	int number_two = 1;

	int sum = number_one + number_two;

	printf("INT_MAX + 1  = %d\n", sum);

      number_one = INT_MIN;
	number_two = -1;
	sum = -1 + INT_MIN;
	printf("-1 + INT_MIN = %d\n", sum);

	return 0;
}

INT_MAX + 1  = -2147483648
-1 + INT_MIN = 2147483647

從上面的小實驗可以看出，當在其類型最大值再加一時，得到的值會是其最小值，而相反的最小值再加負一所得到的值為最大值。

從上圖就可以看出其 `Positive overflow` 得到的值，會從最小範圍上加，而 `Negative overflow` 則是從最大值開始下減。

:::info
**延伸閱讀**
1. [解讀計算機編碼](https://hackmd.io/s/rylUqXLsm#)
:::

> Reference
> [Big-Endian 與Little-Endian 的差異與判斷程式碼- G. T. Wang](https://blog.gtwang.org/programming/difference-between-big-endian-and-little-endian-implementation-in-c/)
> [Bits,Bytes,and Integers CMU CS:APP](http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/lectures/02-03-bits-ints.pdf)