我是小小強(qiáng)，這是我的第5篇原創(chuàng)文章，閱讀需要大約10分鐘。
題目
LintCode:A+B問題
描述
給出兩個(gè)整數(shù)a和b, 求他們的和, 但不能使用+ 等數(shù)學(xué)運(yùn)算符。
- 說明
a和b都是 32位 整數(shù)么？
是的
我可以使用位運(yùn)算符么？
當(dāng)然可以
樣例
如果a=1并且b=2，返回3
思路
題目要求不可以使用加減乘除四則運(yùn)算，那肯定是在移位或者位運(yùn)算上做文章。經(jīng)過分析，兩個(gè)整數(shù)a和b的加法操作，可以等效于(a&b)<<1和a^b相加，也就是進(jìn)位值和非進(jìn)位值，然后又可以繼續(xù)通過這種操作進(jìn)行運(yùn)算，直到達(dá)到一個(gè)不滿足的條件（也就是不在進(jìn)位）為止。這就可以借助循環(huán)或者遞歸操作，關(guān)鍵在于找到結(jié)束循環(huán)和遞歸的條件。對于a&b來說，顯然是有可能不在進(jìn)位，也就是值為0的，這就是一個(gè)有效的判斷條件。
實(shí)現(xiàn)
遞歸實(shí)現(xiàn)
- java代碼
class Solution {
/*
* param a: The first integer
* param b: The second integer
* return: The sum of a and b
*/
public int aplusb(int a, int b) {
// write your code here, try to do it without arithmetic operators.
if(a == 0)
return b;
return aplusb((a&b)<<1, a ^ b);
}
};
- 結(jié)果分析
結(jié)果：結(jié)果通過了LintCode的要求。
分析：這種遞歸只是單純兩個(gè)整數(shù)的操作，在若干次遞歸運(yùn)算之后，很快達(dá)到某個(gè)操作數(shù)為0的條件，從而結(jié)束遞歸。因此速度還是可以達(dá)到要求。
非遞歸實(shí)現(xiàn)
- java代碼
class Solution {
/*
* param a: The first integer
* param b: The second integer
* return: The sum of a and b
*/
public int aplusb(int a, int b) {
// write your code here, try to do it without arithmetic operators.
int sum = 0;
do {
sum = a ^ b;
a = (a & b) << 1;
b = sum;
} while ( a != 0 );
return sum;
}
};
2.結(jié)果分析
結(jié)果：結(jié)果通過了LintCode的要求。
分析：這種操作需要完全理解實(shí)現(xiàn)原理。加法，可以拆分成異或得到的“加法不進(jìn)位”與相與左移1的進(jìn)位的加法，因此，每次遞歸中都進(jìn)行異或、相與左移1，然后，將得到的結(jié)果再做同樣的操作，直到進(jìn)位為0，遞歸停止。
其它優(yōu)化參考
思路：
考慮一個(gè)普通的加法計(jì)算：5＋17＝22
在十進(jìn)制加法中可以分為如下3步進(jìn)行：
忽略進(jìn)位，只做對應(yīng)各位數(shù)字相加，得到12（個(gè)位上5＋7＝12，忽略進(jìn)位，結(jié)果2）；
記錄進(jìn)位，上一步計(jì)算中只有個(gè)位數(shù)字相加有進(jìn)位1，進(jìn)位值為10；
按照第1步中的方法將進(jìn)位值與第1步結(jié)果相加，得到最終結(jié)果22。
下面考慮二進(jìn)制數(shù)的情況（5＝101，17＝10001）：
仍然分3步：
忽略進(jìn)位，對應(yīng)各位數(shù)字相加，得到10100；
記錄進(jìn)位，本例中只有最后一位相加時(shí)產(chǎn)生進(jìn)位1，進(jìn)位值為10（二進(jìn)制）；
按照第1步中的方法將進(jìn)位值與第1步結(jié)果相加，得到最終結(jié)果10110，正好是十進(jìn)制數(shù)22的二進(jìn)制表示。
接下來把上述二進(jìn)制加法3步計(jì)算法用位運(yùn)算替換：
第1步（忽略進(jìn)位）：0＋0＝0，0＋1＝1，1＋0＝0，1＋1＝0，典型的異或運(yùn)算。
第2步：很明顯，只有1＋1會(huì)向前產(chǎn)生進(jìn)位1，相對于這一數(shù)位的進(jìn)位值為10，而10＝(1&1)<<1。
第3步：將第1步和第2步得到的結(jié)果相加，其實(shí)又是在重復(fù)這2步，直到不再產(chǎn)生進(jìn)位為止。
