在不使用 + 的情况下添加两个数字背后的实现逻辑?
Implementation logic behind adding two numbers without using +?
我在网上找到了这段代码。但是,我无法理解以下代码背后的逻辑:
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
}
我们正在添加将整数转换为位并使用按位运算符。
EXOR 即 ^ : 0 ^0 和 1 ^1 =0 ,其他情况给出 1.
AND 即 & 1^1 =1 , ..其他情况给出 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 ,它停止加法和 returns 前一个总和
让我们看一个例子(为简单起见,使用 8 位)
a = 10010110
b = 00111101
a^b
是异或运算,对于一个数字中有 1
而另一个数字中有 0
的地方,它给出 1
。在我们的示例中:
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;
行就可以结束这个过程并给我们一个答案。
这是table加法:
+ 0 1
-- --
0 | 0 1
1 | 1 10
▲
如果你忽略进位 ▲
你会发现它与 XOR 相同 table:
^ 0 1
-- --
0 | 0 1
1 | 1 0
因此,如果您将两个数字与按位异或相结合,您将得到无进位的逐位加法。
现在,什么是进位?只有当两个输入都为 1 时才会出现这种情况。
你可以用 AND 得到它:
& 0 1
-- --
0 | 0 0
1 | 0 1
但是需要向左移动一位后加到和中,因为已经"carried"结束,所以(a & b) << 1
所以你可以计算不带进位的加法和进位本身。你如何在不使用加法的情况下将它们加在一起?简单的!通过递归这个加法的定义!
请参阅@pbabcdefp 关于为什么递归总是终止的回答。
举个例子,5+7
:
5 = 101 (Base 2)
7 = 111 (Base 2)
现在考虑将两个(基数为 2)数字相加:
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
;当你携带一个数字时,它会向左移动一位(因此 (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 = 010
B = 1010
A^B = 1000 (sum without carrying)
A&B = 0010 (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)
现在没有东西可以带了-所以我们可以停下来,答案是1100 (base 2) = 12 (base 10)
。
该算法只是将十进制加法实现为(普通)二进制加法,使用 or
s 进行加法运算,并使用移位的 and
s 来查找进位,并将递归直到没有更多内容进位(这总是会发生,因为位移位每次都会向进位附加另一个零,因此每次递归至少多一位不会每次都生成进位值)。
我在网上找到了这段代码。但是,我无法理解以下代码背后的逻辑:
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
}
我们正在添加将整数转换为位并使用按位运算符。
EXOR 即 ^ : 0 ^0 和 1 ^1 =0 ,其他情况给出 1.
AND 即 & 1^1 =1 , ..其他情况给出 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 ,它停止加法和 returns 前一个总和
让我们看一个例子(为简单起见,使用 8 位)
a = 10010110
b = 00111101
a^b
是异或运算,对于一个数字中有 1
而另一个数字中有 0
的地方,它给出 1
。在我们的示例中:
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;
行就可以结束这个过程并给我们一个答案。
这是table加法:
+ 0 1
-- --
0 | 0 1
1 | 1 10
▲
如果你忽略进位 ▲
你会发现它与 XOR 相同 table:
^ 0 1
-- --
0 | 0 1
1 | 1 0
因此,如果您将两个数字与按位异或相结合,您将得到无进位的逐位加法。
现在,什么是进位?只有当两个输入都为 1 时才会出现这种情况。
你可以用 AND 得到它:
& 0 1
-- --
0 | 0 0
1 | 0 1
但是需要向左移动一位后加到和中,因为已经"carried"结束,所以(a & b) << 1
所以你可以计算不带进位的加法和进位本身。你如何在不使用加法的情况下将它们加在一起?简单的!通过递归这个加法的定义!
请参阅@pbabcdefp 关于为什么递归总是终止的回答。
举个例子,5+7
:
5 = 101 (Base 2)
7 = 111 (Base 2)
现在考虑将两个(基数为 2)数字相加:
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
;当你携带一个数字时,它会向左移动一位(因此 (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 = 010
B = 1010
A^B = 1000 (sum without carrying)
A&B = 0010 (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)
现在没有东西可以带了-所以我们可以停下来,答案是1100 (base 2) = 12 (base 10)
。
该算法只是将十进制加法实现为(普通)二进制加法,使用 or
s 进行加法运算,并使用移位的 and
s 来查找进位,并将递归直到没有更多内容进位(这总是会发生,因为位移位每次都会向进位附加另一个零,因此每次递归至少多一位不会每次都生成进位值)。