public int add(int a, int b){
while (b != 0){
int carry = (a & b) ;
a = a ^ b;
b = carry << 1;
}
return a;
}
这是使用按位运算计算两个整数之和的代码。
如果我手动/以编程方式计算,我发现它适用于每个整数。
但我无法弄清楚 a
和 carry
的中间值之间的任何关系。
以及为什么进位乘以 2 分配给 b
?
PS:我在这里找到了一个答案 Bitwise Multiply and Add in Java 但这是乘法而不是加法。
最佳答案
小学的第一次记忆加法。例如26 + 147 = 173。您从 6+7=13 开始,所以您将 3 放入和中,然后进位,依此类推 - 即:您添加两位数字并在必要时进位一个。
carry: 1
a: 26
b: 147
-----------------
sum: 173
该代码对二进制数执行几乎相同的操作,但稍作调整。它不是一次取一个数字的位置,而是一次取完所有。代码不是在 i 中包括位置 i-1 的进位(即在添加 2 和 4 时包括 1),而是在第二次迭代中添加所有龋齿。所以它的作用是:026+147 = 163 + 010 = 173 + 000
对于二进制数 a=6=00110 和 b=7=00111 你得到
首先你找到进位;这就是所有 a
都在的位置和 b
设置了位:int carry = (a & b) ;
然后 id 进行数字相加,忽略进位,并将其存储在 a
中: a = a ^ b;
这将回应 6+7=3
在示例中。
最后一部分将进位移动到下一个数字位置,即确保示例中的 1 进位从 1“移动”到 10:carry << 1;
只要总和中没有包含进位,while 循环就会继续。
关于java - 为什么这个加法代码(使用按位运算)在 java 中有效,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17342042/