算術運算

整數的算術運算也不總符合我們的常識，比如下面這個例子：

// Java語言
public static void main(String[] args) {
    int i1 = 2147483647;
    int i2 = 1;
    System.out.printf("2147483647+1=%d\\n", i1+i2);
}
// 輸出結果：
2147483647+1=-2147483648

兩個正數 2147483647 和 1 相加，實際運行結果卻是一個負數 -2147483648。原因是，運算結果超出了 int 類型的表示范圍，我們把這種現象稱作 溢出 。

接下來，我們將介紹整數類型常見的幾種算術運算，包括當運算出現溢出時，計算機系統的處理方式。

加法

（1）無符號整數加法運算

對兩個 w 位的無符號整數 ，有 ；如果仍用一個 w 位的整數表示相加結果，那么當結果在 范圍時，也即結果需要 w + 1 位表示時，運算就產生溢出了。

如果出現溢出，系統會對結果進行截斷，只保留低 w 位 。

比如，w = 4 場景下的一些例子：

因此，如果用 表示 w 位無符號整數的加法運算，那么它有如下規則：

其中，溢出場景因為對結果的進行截斷，舍去了 位，所以結果需要減去 。

（2）有符號整數加法運算

對兩個 w 位的有符號整數 ，有 ；如果仍用一個 w 位的整數表示相加結果，那么當結果在 和 范圍時，運算就產生溢出了。

比如，w = 4 場景下的一些例子：

由上述例子可知， 兩個 w 位的負數相加，即使結果需要 w + 1 位表示，也可能是正常場景。這取決于截斷位 w 位后的最高位，為 1 則還屬于正常場景，為 0 則屬于溢出場景 。

因此，如果用 表示 w 位有符號整數的加法運算，那么它有如下規則：

• 正溢出場景下 ，原本 ，但按照補碼編碼方式，實際變成了 ，所以就有 。
• 負溢出場景下 ，w 位一定是 0，原本 ，結果截斷之后，實際變成了 ，所以就有 。

為什么負溢出場景下，w 位一定是 0 ？

負溢出場景出現的條件是 ，也即 :

如果要使上述不等式成立， 必然為 0.

前面很多公式，但記住這個就行， 無符號整數和有符號整數的加法運算規則，本質都是一樣的，可以拆解成 4 步 ：

1. 先計算出真實加法運算的結果值。
2. 對結果值用 w + 1 位二進制表示。
3. 再將 w + 1 位的二進制結果截斷，保留低 w 位。
4. 將截斷后的 w 位二進制值轉換回十進制整數，得到最終結果。無符號整數用無符號編碼，有符號整數用補碼編碼。

取反

取反，也即求相反數，給定一個整數 ，那么它的相反數 ，也即滿足 。

（1）無符號整數的取反

對一個 w 位的無符號整數 ，對它取反，也即找到一個整數 ，使得 ：

• 當 ，那么很容易得出 ；
• 當 x > 0，只有在溢出場景才會存在 的可能。由前文可知，無符號整數加法溢出場景下， 時，有，。

因此，如果用 表示 w 位無符號整數的取反運算，那么它有如下規則：

比如，w = 8 場景下的例子：

// C++
int main() {
    uint8_t i1 = 0;
    uint8_t i2 = -i1;
    printf("i1=%u\\n", i1);
    printf("-i1=%u\\n", i2);

    uint8_t i3 = 100;
    uint8_t i4 = -i3;
    printf("i3=%u\\n", i3);
    printf("-i3=%u\\n", i4);
    printf("2^8-i3=256-%u=%u\\n", i3, 256-i3);
    return 0;
}
// 輸出結果
i1=0
-i1=0
i3=100
-i3=156
2^8-i3=256-100=156

（2）有符號整數的取反

對一個 w 位的有符號整數 ，對它取反，也即找到一個整數 ，使得 ：

• 當 ，很容易得出 ，因為此時 ，仍是有效的范圍。
• 當 ，因為 已經不再有效范圍內，所以只能是溢出場景。而 ，截斷為 w 之后，剛好為 0。所以，此時 。

因此，如果用 表示 w 位有符號整數的取反運算，那么它有如下規則：

比如，w = 8 場景下的例子：

// C++
int main() {
    int8_t i1 = -128;
    int8_t i2 = -i1;
    printf("i1=%d\\n", i1);
    printf("-i1=%d\\n", i2);

    int8_t i3 = 100;
    int8_t i4 = -i3;
    printf("i3=%d\\n", i3);
    printf("-i3=%d\\n", i4);
    return 0;
}
// 輸出結果
i1=-128
-i1=-128
i3=100
-i3=-100

乘法

前面介紹加法時說過，無符號整數和有符號整數的加法運算都可以拆成 4 步，這對乘法運算也適用。

對于無符號整數 ，那么 ，即無符號整數的乘法運算結果最多需要 2w 位來表示。

比如，w = 8 時，無符號整數的例子：

// C++
int main() {
    uint8_t i1 = 100;
    uint8_t i2 = 2;
    uint8_t i3 = i1 * i2;
    printf("normal: i1 * i2 = %d * %d = %d\\n", i1, i2, i3);

    uint8_t i4 = 100;
    uint8_t i5 = 3;
    uint8_t i6 = i4 * i5;
    printf("overflow: i4 * i5 = %d * %d = %d\\n", i4, i5, i6);
    return 0;
}
// 輸出結果
normal: i1 * i2 = 100 * 2 = 200
overflow: i4 * i5 = 100 * 3 = 44

對于有符號整數 ，那么 ，即有符號整數的乘法運算結果最多也需要 2w 位來表示。

比如，w = 8 時，有符號整數的例子：

// C++
int main() {
    int8_t i1 = -50;
    int8_t i2 = 2;
    int8_t i3 = i1 * i2;
    printf("normal: i1 * i2 = %d * %d = %d\\n", i1, i2, i3);

    int8_t i4 = -128;
    int8_t i5 = 127;
    int8_t i6 = i4 * i5;
    printf("overflow: i4 * i5 = %d * %d = %d\\n", i4, i5, i6);
    return 0;
}
// 輸出結果
normal: i1 * i2 = -50 * 2 = -100
overflow: i4 * i5 = -128 * 127 = -128

大部分機器上，乘法運算消耗 3 ~ 10 個 CPU 時鐘周期，而加法運算和位運算只消耗 1 個時鐘周期，所以，追求極致性能的程序都會想辦法通過加法運算和位運算來替代乘法運算。

如果不考慮截斷，對 左移 k 位，會得到:

也即，對 左移 k 位 相當于乘以 。

如果考慮截斷，就會存在溢出場景，對于 w 位的整數，左移 k 位效果也等同于 或 。

比如，w = 8 時，無符號整數的例子：

// C++
int main() {
    uint8_t i1 = 100;
    uint8_t i2 = 4;
    uint8_t i3 = i1 * i2;
    printf("i1 * i2 = %d * %d = %d\\n", i1, i2, i3);

    uint8_t k = 2;
    uint8_t i4 = i1 << k;
    printf("i1 << k = %d << %d = %d\\n", i1, k, i4);
    return 0;
}
// 輸出結果
i1 * i2 = 100 * 4 = 144
i1 << k = 100 << 2 = 144

有符號整數的例子：

// C++
int main() {
    int8_t i1 = -50;
    int8_t i2 = 4;
    int8_t i3 = i1 * i2;
    printf("i1 * i2 = %d * %d = %d\\n", i1, i2, i3);

    int8_t k = 2;
    int8_t i4 = i1 << k;
    printf("i1 << k = %d << %d = %d\\n", i1, k, i4);
    return 0;
}
// 輸出結果
i1 * i2 = -50 * 4 = 56
i1 << k = -50 << 2 = 56

那么，對于與任意常數 K 的相乘，有沒可能轉換為移位操作 ？

任意常數 K，可以表示成 的形式，也即，由一系列連續的 0 和 連續的 1 組成，比如 14 可以表示成 。

假設只存在一個連續的 1 序列，從高到低， 位于 n 到 m 位，比如 14 中，n = 3，m = 1，那么：

比如， 就可以表示成 或者 ：

// C++
int main() {
    int8_t x = 5;
    int8_t K = 14;
    printf("x * 14 = %d\\n", x*K);
    printf("(x<<3) + (x<<2) + (x<<1) = %d\\n", (x<<3)+(x<<2)+(x<<1));
    printf("(x<<4) - (x<<1) = %d\\n", (x<<4)-(x<<1));
    return 0;
}
// 輸出結果
x * 14 = 70
(x<<3) + (x<<2) + (x<<1) = 70
(x<<4) - (x<<1) = 70

同理，當 K 的二進制表示，存在多個連續的 1 序列時，也成立。

除法

除法運算比乘法運算更慢，通常需要 30 個 CPU 時鐘以上 。同理， 也可以轉換成右移運算，注意結果的取整：

// C++
int main() {
    int8_t x = -50;
    int8_t K = 4;
    printf("x / 4 = %d\\n", x/K);
    printf("x >> 2 = %d\\n", x>>2);
    printf("(x+(1<<2))>>2 = %d\\n", (x+(1<<2))>>2);

    uint8_t y = 50;
    uint8_t Z = 4;
    printf("y / 4 = %d\\n", y/Z);
    printf("y >>> 2 = %d\\n", y>>2);
    printf("(y+(1<<2))>>>2 = %d\\n", (y+(1<<2))>>2);
    return 0;
}
// 輸出結果
x / 4 = -12
x >> 2 = -13
(x+(1<<2))>>2 = -12

y / 4 = 12
y >>> 2 = 12
(y+(1<<2))>>>2 = 13