算術(shù)運算

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

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

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

接下來，我們將介紹整數(shù)類型常見的幾種算術(shù)運算，包括當(dāng)運算出現(xiàn)溢出時，計算機系統(tǒng)的處理方式。

加法

（1）無符號整數(shù)加法運算

對兩個 w 位的無符號整數(shù) ，有 ；如果仍用一個 w 位的整數(shù)表示相加結(jié)果，那么當(dāng)結(jié)果在 范圍時，也即結(jié)果需要 w + 1 位表示時，運算就產(chǎn)生溢出了。

如果出現(xiàn)溢出，系統(tǒng)會對結(jié)果進行截斷，只保留低 w 位 。

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

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

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

（2）有符號整數(shù)加法運算

對兩個 w 位的有符號整數(shù) ，有 ；如果仍用一個 w 位的整數(shù)表示相加結(jié)果，那么當(dāng)結(jié)果在 和 范圍時，運算就產(chǎn)生溢出了。

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

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

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

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

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

負溢出場景出現(xiàn)的條件是 ，也即 :

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

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

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

取反

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

（1）無符號整數(shù)的取反

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

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

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

比如，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;
}
// 輸出結(jié)果
i1=0
-i1=0
i3=100
-i3=156
2^8-i3=256-100=156

（2）有符號整數(shù)的取反

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

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

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

比如，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;
}
// 輸出結(jié)果
i1=-128
-i1=-128
i3=100
-i3=-100

乘法

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

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

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

// 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;
}
// 輸出結(jié)果
normal: i1 * i2 = 100 * 2 = 200
overflow: i4 * i5 = 100 * 3 = 44

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

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

// 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;
}
// 輸出結(jié)果
normal: i1 * i2 = -50 * 2 = -100
overflow: i4 * i5 = -128 * 127 = -128

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

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

也即，對 左移 k 位 相當(dāng)于乘以 。

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

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

// 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;
}
// 輸出結(jié)果
i1 * i2 = 100 * 4 = 144
i1 << k = 100 << 2 = 144

有符號整數(shù)的例子：

// 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;
}
// 輸出結(jié)果
i1 * i2 = -50 * 4 = 56
i1 << k = -50 << 2 = 56

那么，對于與任意常數(shù) K 的相乘，有沒可能轉(zhuǎn)換為移位操作 ？

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

假設(shè)只存在一個連續(xù)的 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;
}
// 輸出結(jié)果
x * 14 = 70
(x<<3) + (x<<2) + (x<<1) = 70
(x<<4) - (x<<1) = 70

同理，當(dāng) K 的二進制表示，存在多個連續(xù)的 1 序列時，也成立。

除法

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

// 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;
}
// 輸出結(jié)果
x / 4 = -12
x >> 2 = -13
(x+(1<<2))>>2 = -12

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