題目

題目：寫(xiě)一個(gè)函數(shù)，求兩個(gè)整數(shù)之和，要求在函數(shù)體內(nèi)不得使用+、-、*、/四則運(yùn)算符號(hào)。

思路

雖然一看就知道是使用位運(yùn)算做這個(gè)題目，但還是沒(méi)做出來(lái)。

先理解一下10進(jìn)制是如何做加法的。例如5+7=12，分為3步。

1. 先不考慮進(jìn)位值，5+7得到2.
2. 再計(jì)算進(jìn)位值，個(gè)位上5+7的進(jìn)位為1，所以進(jìn)位為1*10=10 (要乘以10是因?yàn)閭€(gè)位上進(jìn)一相當(dāng)于加10).
3. 重復(fù)1，2，直到?jīng)]有進(jìn)位制產(chǎn)生，就結(jié)束了。例如本題就是再次計(jì)算2+10，不考慮進(jìn)位為12，計(jì)算進(jìn)位得到0，所以最終結(jié)果為32.

對(duì)于10進(jìn)制，還是用到了加法和乘法運(yùn)算。

對(duì)于2進(jìn)制的計(jì)算也是一樣的，由于二進(jìn)制的特殊，還可以用位運(yùn)算替代加法運(yùn)算和乘法運(yùn)算。

按位異或：1^1=0 0^0=0 1^0=1 0^1=1

按位與 ：1&1=1 0&0=0 1&0=0 0&1=0

所以按位異或等價(jià)于不考慮進(jìn)位的加法，按位與左移1位表示進(jìn)位值。

同樣考慮5+7，注：5=101，7=111，

1. 先不考慮進(jìn)位值，101^111=010
2. 計(jì)算進(jìn)位值，101&111=101，需要再左移一位，得到1010
3. 重復(fù)1，2
   1. 先不考慮進(jìn)位值,0010^1010=1000
   2. 計(jì)算進(jìn)位值，0010&1010=0010，再左移一位，得到00100
   3. 重復(fù)1，2
      1. 先不考慮進(jìn)位值,01000^00100=01100
      2. 計(jì)算進(jìn)位值，01000&00100=0，左移之后還是0
      3. 因?yàn)檫M(jìn)位值為0，所以計(jì)算可以終止，最終結(jié)果為01100，即12

代碼

class Solution {
public:
    int Add(int num1, int num2)
    {
        while(num2 != 0){ //沒(méi)有進(jìn)位的時(shí)候可以停止迭代
            int temp = num1 ^ num2; //不考慮進(jìn)位的加法
            num2 = (num1 & num2) << 1; //進(jìn)位值儲(chǔ)存在num2中
            num1 = temp;//將不考慮進(jìn)位的加法儲(chǔ)存在num1中，下次再次計(jì)算num1+num2
        }
        return num1;
    }
};

總結(jié)

• 加法運(yùn)算可以拆解成不考慮進(jìn)位的加法和只計(jì)算進(jìn)位值兩部分

我的segmentfault鏈接