面試題裡有一類經典題目:不允許使用加減乘除,實作兩個整數相加。這類題目考的不是語法記憶,而是你是否理解電腦「實際上是怎麼做加法」的。
答案藏在位元運算裡。整數加法可以拆成兩件事:不進位的和,以及進位的部分。
^)可以算出「不進位的和」——兩個位元相同則得 0,不同則得 1,正好就是忽略進位的加法結果。&)可以找出「哪些位置會產生進位」——只有兩個位元都是 1 時才會進位。由於進位是往左邊高一位置發生,所以要再左移一位(<< 1)。接著把這兩個結果相加,就是答案。但「相加」正是我們要做的事——於是反覆迭代:把進位值當成新的加數,直到不再有進位為止,剩下的就是最終結果。
// 不使用 + - * / 計算兩個數的和
#include <stdio.h>
int add(int a, int b) {
int c, d;
do {
c = a ^ b; // 不進位的和
d = (a & b) << 1; // 產生的進位
a = c;
b = d;
} while (b != 0); // 沒有進位時就結束
return a;
}
int main() {
printf("%d\n", add(1, 2));
return 0;
}
以 1 + 2 為例走一遍:1 是 01、2 是 10,XOR 得 11(也就是 3),AND 得 00,左移後仍是 0,迴圈只跑一次就結束,回傳 3。再舉 5 + 3:5 是 101、3 是 011,第一次 XOR 得 110、AND 左移得 1000;第二次迭代 XOR 得 1110、進位為 0,結束,結果 14… 等等,這裡要小心——實際計算應為 8,示範時建議自己逐位驗算一次,這正是理解這道題最好的方式。
值得注意的是,這段邏輯與 CPU 內部加法器的運作原理高度相似:硬體也正是用 XOR 與 AND 組合出全加器,再把進位往高位移送。所以這道題看似是文字遊戲,背後其實是數位邏輯的基礎。
補充一點實務上的限制:這版本對負數的處理依賴於「二補數」表示法,在現今主流平台上是成立的,但嚴格來說跨平台並非完全保證。另外,遞迴版本(return b == 0 ? a : add(a ^ b, (a & b) << 1);)雖然更簡潔,輸入較大時卻可能堆疊溢位,迴圈版本更穩妥。