为什么这个用于添加的代码(使用按位运算)在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和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循环就会继续.