算術(shù)運(yùn)算

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

// Java語(yǔ)言
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

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

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

加法

（1）無(wú)符號(hào)整數(shù)加法運(yùn)算

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

如果出現(xiàn)溢出，系統(tǒng)會(huì)對(duì)結(jié)果進(jìn)行截?cái)?，只保留?w 位 。

比如，w = 4 場(chǎng)景下的一些例子：

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

其中，溢出場(chǎng)景因?yàn)閷?duì)結(jié)果的進(jìn)行截?cái)?，舍去? 位，所以結(jié)果需要減去 。

（2）有符號(hào)整數(shù)加法運(yùn)算

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

比如，w = 4 場(chǎng)景下的一些例子：

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

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

• 正溢出場(chǎng)景下 ，原本 ，但按照補(bǔ)碼編碼方式，實(shí)際變成了 ，所以就有 。
• 負(fù)溢出場(chǎng)景下 ，w 位一定是 0，原本 ，結(jié)果截?cái)嘀?，?shí)際變成了 ，所以就有 。

為什么負(fù)溢出場(chǎng)景下，w 位一定是 0 ？

負(fù)溢出場(chǎng)景出現(xiàn)的條件是 ，也即 :

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

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

1. 先計(jì)算出真實(shí)加法運(yùn)算的結(jié)果值。
2. 對(duì)結(jié)果值用 w + 1 位二進(jìn)制表示。
3. 再將 w + 1 位的二進(jìn)制結(jié)果截?cái)?，保留?w 位。
4. 將截?cái)嗪蟮?w 位二進(jìn)制值轉(zhuǎn)換回十進(jìn)制整數(shù)，得到最終結(jié)果。無(wú)符號(hào)整數(shù)用無(wú)符號(hào)編碼，有符號(hào)整數(shù)用補(bǔ)碼編碼。

取反

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

（1）無(wú)符號(hào)整數(shù)的取反

對(duì)一個(gè) w 位的無(wú)符號(hào)整數(shù) ，對(duì)它取反，也即找到一個(gè)整數(shù) ，使得 ：

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

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

比如，w = 8 場(chǎng)景下的例子：

// 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）有符號(hào)整數(shù)的取反

對(duì)一個(gè) w 位的有符號(hào)整數(shù) ，對(duì)它取反，也即找到一個(gè)整數(shù) ，使得 ：

• 當(dāng) ，很容易得出 ，因?yàn)榇藭r(shí) ，仍是有效的范圍。
• 當(dāng) ，因?yàn)? 已經(jīng)不再有效范圍內(nèi)，所以只能是溢出場(chǎng)景。而 ，截?cái)酁?w 之后，剛好為 0。所以，此時(shí) 。

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

比如，w = 8 場(chǎng)景下的例子：

// 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í)說(shuō)過(guò)，無(wú)符號(hào)整數(shù)和有符號(hào)整數(shù)的加法運(yùn)算都可以拆成 4 步，這對(duì)乘法運(yùn)算也適用。

對(duì)于無(wú)符號(hào)整數(shù) ，那么 ，即無(wú)符號(hào)整數(shù)的乘法運(yùn)算結(jié)果最多需要 2w 位來(lái)表示。

比如，w = 8 時(shí)，無(wú)符號(hào)整數(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

對(duì)于有符號(hào)整數(shù) ，那么 ，即有符號(hào)整數(shù)的乘法運(yùn)算結(jié)果最多也需要 2w 位來(lái)表示。

比如，w = 8 時(shí)，有符號(hào)整數(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

大部分機(jī)器上，乘法運(yùn)算消耗 3 ~ 10 個(gè) CPU 時(shí)鐘周期，而加法運(yùn)算和位運(yùn)算只消耗 1 個(gè)時(shí)鐘周期，所以，追求極致性能的程序都會(huì)想辦法通過(guò)加法運(yùn)算和位運(yùn)算來(lái)替代乘法運(yùn)算。

如果不考慮截?cái)?，?duì) 左移 k 位，會(huì)得到:

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

如果考慮截?cái)啵蜁?huì)存在溢出場(chǎng)景，對(duì)于 w 位的整數(shù)，左移 k 位效果也等同于 或 。

比如，w = 8 時(shí)，無(wú)符號(hào)整數(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

有符號(hào)整數(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

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

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

假設(shè)只存在一個(gè)連續(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 的二進(jìn)制表示，存在多個(gè)連續(xù)的 1 序列時(shí)，也成立。

除法

除法運(yùn)算比乘法運(yùn)算更慢，通常需要 30 個(gè) CPU 時(shí)鐘以上 。同理， 也可以轉(zhuǎn)換成右移運(yù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