在不使用+的情況下添加兩個數字後的執行邏輯？

我在網上找到了這段代碼。但是，我無法獲得以下代碼的邏輯：在不使用+的情況下添加兩個數字後的執行邏輯？

public static int add(int a, int b) { 
    if (b == 0) return a; 
    int sum = a^b; // add without carrying 
    System.out.println("sum is : "+sum); 
    int carry = (a & b) << 1; // carry, but don’t add 
    return add(sum, carry); // recurse 
}

來源

2015-04-18 UserJS

讓我們來看一個例子（使用爲了簡化8位）

a = 10010110 
    b = 00111101

a^b是異或，這給1對於其中一個號碼爲1而另一個號碼爲0的地點。在我們的例子：

a^b = 10101011

由於0 + 0 = 0，0 + 1 = 1和1 + 0 = 1，唯一列留下來處理是有兩個數字的1的人。在我們的示例中，a^b短於任何回答

 00010100 
    + 00010100

是。二進制，1 + 1 = 10，所以答案上述總和是

00101000

或(a & b) << 1。因此，a^b和(a & b) << 1的總和與a + b相同。

因此，假設過程保證終止，答案將是正確的。但是該過程將終止，因爲每次我們遞歸調用sum時，由於移位<<，第二個參數在末尾至少還有一個0。因此，我們保證最終會得到完全由0組成的第二個參數，因此行if (b == 0) return a;可以結束該過程並給我們一個答案。

來源

2015-04-19 00:26:55

我們正在將整數轉換爲位並使用按位運算符。

EXOR即^：0^0和1^1 = 0，其它情況下給予1

和IE & 1^1 = 1，..other例得到0.

< <或左移。即向左移位並追加0位：0010變成0100

例如，

add(2,3) 

2= 0010 
3=0011 

exor both : to get initial sum : 0001 

carry : a &b = 0010 

Left shift by 1 bit : 0100 i.e 4 

add(1,4) 

exor both : 0001 0100 and u get 0101 i.e 5 

carry = 0000 <<1 i.e 0000 ..

因爲進位是0，則停止加入，並且返回前面的總和

來源

2015-04-19 00:20:27

這是除了表：

如果忽略進位▲你會發現它是一樣的XOR表：

^ 0 1 
    -- -- 
0 | 0 1 
1 | 1 0

所以，如果你結合兩個具有按位異或的數字，您可以逐位添加而無需進位。

現在，什麼是進位？當兩個輸入都是1時，只有一點。

你可以得到與AND：

& 0 1 
    -- -- 
0 | 0 0 
1 | 0 1

但需要被添加到總和正在移動一個位置到左邊後，因爲它是「攜帶」了，因此(a & b) << 1

所以你可以計算加法運算和運算本身。你如何將它們加在一起而不使用加法？簡單！通過遞歸這個加法的定義！

請參閱@ pbabcdefp關於爲什麼遞歸總是終止的答案。

來源

2015-04-19 00:29:00 Tobia

考慮，作爲一個例子，5+7：

5  = 101 (Base 2) 
7  = 111 (Base 2)

現在考慮添加兩個（基數爲2）數字：的A+B

0+0 = 0 = 0 carry 0 
1+0 = 1 = 1 carry 0 
0+1 = 1 = 1 carry 0 
1+1 = 10 = 0 carry 1

總和（不攜帶）是A^B和進位是A&B;並且當您攜帶一個號碼時，它會向左移一位數（因此(A&B)<<1）。

所以：

5 = 101 (Base 2) 
7 = 111 (Base 2) 
5^7 = 010 (sum without carrying) 
5&7 = 101 (the carry shifted left)

然後，我們可以改乘添加進：

A' = 1000 
B' = 100 (without the leading zeros) 
A'^B' = 1100 (sum without carrying) 
A'&B' = 0000 (the carry shifted left)

現在：

A = 010 
B = 1010 
A^B = 1000 (sum without carrying) 
A&B = 0010 (the carry shifted left)

然後，我們可以，因爲我們還有更多攜帶再次遞歸沒有東西可以攜帶 - 所以我們可以停下來，答案是1100 (base 2) = 12 (base 10)。

該算法正在實施十進制加法作爲（longhand）二進制加法使用or s來添加和bitshifted and s來找到進位並將遞歸，直到沒有什麼更多要進行（這將始終發生的位移每次對進位附加零，所以每次遞歸至少再有一位不會產生進位值）。

來源

2015-04-19 00:33:43 MT0

在不使用+的情況下添加兩個數字後的執行邏輯？

回答

相關問題