摘要

劍指 Offer 65. 不用加減乘除做加法

一、位運(yùn)算

有符號整數(shù)通常用補(bǔ)碼來表示和存儲，補(bǔ)碼具有如下特征：

• 正整數(shù)的補(bǔ)碼與原碼相同；負(fù)整數(shù)的補(bǔ)碼為其原碼除符號位外的所有位取反后加 11。
• 可以將減法運(yùn)算轉(zhuǎn)化為補(bǔ)碼的加法運(yùn)算來實(shí)現(xiàn)。
• 符號位與數(shù)值位可以一起參與運(yùn)算。

思路和算法：雖然題目只要求了不能使用運(yùn)算符+、-、*和/，但是原則上來說也不宜使用類似的運(yùn)算符+=、-=、*=和/=，以及sum等方法。于是，我們使用位運(yùn)算來處理這個問題。首先，考慮兩個二進(jìn)制位相加的四種情況如下：

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0 (進(jìn)位)

可以發(fā)現(xiàn)，對于整數(shù)a和b：

• 在不考慮進(jìn)位的情況下，其無進(jìn)位加法結(jié)果為 a⊕b。
• 而所有需要進(jìn)位的位為a&b，進(jìn)位后的進(jìn)位結(jié)果為 (a & b) << 1。

于是，我們可以將整數(shù)a和 b的和，拆分為a和b的無進(jìn)位加法結(jié)果與進(jìn)位結(jié)果的和。因?yàn)槊恳淮尾鸱侄伎梢宰屝枰M(jìn)位的最低位至少左移一位，又因?yàn)閍和 b可以取到負(fù)數(shù)，所以我們最多需要 log?(max_int)次拆分即可完成運(yùn)算。因?yàn)橛蟹栒麛?shù)用補(bǔ)碼來表示，所以以上算法也可以推廣到0 和負(fù)數(shù)。

class Solution {public int add(int a, int b) {while (b != 0) {int carry = (a & b) << 1;a = a ^ b;b = carry;}return a;}
}

復(fù)雜度分析

• 時間復(fù)雜度：O(log?(max_int))，其中我們將執(zhí)行位運(yùn)算視作原子操作。
• 空間復(fù)雜度：O(1)。

博文參考