java - 为什么这个加法代码(使用按位运算)在 java 中有效

Question

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但这是乘法而不是加法。

Answer 1

小学的第一次记忆加法。例如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 循环就会继续。