山東電力建設(shè)第一工程公司網(wǎng)站怎么讓客戶主動找你
摘要
劍指 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)。