一、描述
寫一個函數(shù)，求兩個整數(shù)之和，要求在函數(shù)體內(nèi)不得使用+、-、*、/四則運(yùn)算符號，本題OJ鏈接
數(shù)據(jù)范圍：兩個數(shù)都滿足 ?10≤n≤1000
進(jìn)階：空間復(fù)雜度 O(1)，時間復(fù)雜度 O(1)文章來源：http://www.zghlxwxcb.cn/news/detail-691110.html
二、方法
分析：本題要求不能使用+、-、*、/，所以我們應(yīng)該從二進(jìn)制的角度去考慮，因?yàn)槎M(jìn)制的加法可以通過與（&）、或（|）、左移（<<）和或（|）來完成，并且二進(jìn)制的話不用考慮正負(fù)數(shù)，直接對補(bǔ)碼進(jìn)行加法運(yùn)算就行。但是具體怎么加呢？人去計(jì)算二進(jìn)制相加很簡單，直接通過肉眼就可以判斷哪里要進(jìn)位，哪里不需要，然后再最終相加，但是電腦不會這樣做，那該怎么辦呢？
思路：通過十進(jìn)制相加思想推導(dǎo)出二進(jìn)制相加思想
十進(jìn)制相加思想（和平常的直接加法不同）：
1、如果兩數(shù)相加每一位都不會產(chǎn)生進(jìn)位，則直接相加就是最終結(jié)果
2、如果兩數(shù)相加會產(chǎn)生進(jìn)位（無論哪幾位產(chǎn)生進(jìn)位都行），先計(jì)算不考慮進(jìn)位的相加結(jié)果，記作a，再計(jì)算進(jìn)位，記作b，然后把a(bǔ)和b看作新得到的兩個數(shù)相加，看是情況1還是情況2，一直這樣下去，直到計(jì)算出結(jié)果
例如，如下圖所示：
二進(jìn)制相加思想：
和上面十進(jìn)制相加思想一樣，只不過：
1、有沒有產(chǎn)生進(jìn)位通過相與來判斷，相與結(jié)果為0，沒有進(jìn)位，否則，有進(jìn)位。沒有進(jìn)位，兩數(shù)相或就是最終結(jié)果；有進(jìn)位，需要進(jìn)一步計(jì)算，與的結(jié)果左移一位就是最終的進(jìn)位
2、不考慮進(jìn)位的相加結(jié)果通過異或可以完成
例如，如下圖所示：
分析：產(chǎn)生多少次進(jìn)位，就循環(huán)多少次，最多不超過32次進(jìn)位，時間復(fù)雜度O(1)，空間復(fù)雜度O(1)
代碼實(shí)現(xiàn)：文章來源地址http://www.zghlxwxcb.cn/news/detail-691110.html
int Add(int a, int b )
{
int n1 = 0;
int n2 = 0;
while(a & b) //判斷是否有進(jìn)位，有進(jìn)位一直循環(huán)計(jì)算，直到?jīng)]有進(jìn)位為止
{
n1 = (a & b) << 1; //最終的進(jìn)位
n2 = a ^ b; //不考慮進(jìn)位的相加結(jié)果
a = n1; //作為新的a
b = n2; //作為新的b
}
return a | b; //此時a&b不會產(chǎn)生進(jìn)位，計(jì)算最終結(jié)果
}
到了這里，關(guān)于不用加減乘除做加法的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
