題目描述
Write a function that adds two numbers. You should not use + or any arithmetic operators.
Note:
aandbmay be 0 or negative.- The result fits in 32-bit integer.
解題思路
不用加法運算子實作加法，我們來看計算機底層是如何實作加法的，
1+1=10、1+0=1、0+1=1、0+0=0在這四種情況中，若不考慮進位，則
1+1=0、1+0=1、0+1=1、0+0=0，我們可以看到在不考慮進位的情況下，兩二進制位相加的結果就是異或的結果，
而如果考慮進位，那么只有1+1的情況下有進位，即&運算為1，代表進位，
考慮數A、B，其二進制表示:\(A_2\)、\(B_2\)，則有：
\[A_2+B_2=(A_2 {\wedge} B_2)+(A_2{\&}B_2)<<1 \]\(A_2 {\wedge} B_2\)表示不帶進位的數，\((A_2{\&}B_2)<<1\)表示進位數，
兩者相加即為結果，
例如，要計算：1101+1001
不考慮進位：1101^1001=0100
考慮進位：1101&1001=1001，而1001<<1=10010
兩者求和：0100+10010=10110即為結果，
但是上面對進位和不進位的兩部分求和還是用到了加法，不能用加法怎么辦？遞回地將兩部分視為新的\(A_2\)、\(B_2\)，直到進位為0，
考慮負數和0？由于計算機底層采用補碼，符號位參與運算，因此，上述方法對于計算正負數還是0的加法沒有區別，
代碼
遞回版
class Solution {
public int add(int a, int b) {
if((a & b) == 0){
return a ^ b;//沒有進位，直接回傳
}
return add(a ^ b,(a & b) << 1);
}
}
非遞回版
class Solution {
public int add(int a, int b) {
while(b!=0){
int tmp = a ^ b;//不考慮進位
b = (a & b) << 1;//單獨考慮進位
a = tmp;//由于不能相加，遞回地計算進位和不進位的值
}//直到進位為0
return a;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/278381.html
標籤：其他
上一篇：資料流中數字的秩