位运算实现加法

位运算实现加法

Posted by Jae on May 23, 2019

在计算机的底层使用位运算计算加法,对于减法运算使用其补码转成加法运算的形式;假设不考虑进位,计算两个一位数的加法

1 + 1 = 0 向上进了一个1
1 + 0 = 1
0 + 1 = 1
0 + 0 = 0

从上面的计算结果可以看出,可以使用异或运算来代替+

1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0

这样就完成了简单的一位数加法,但是进行两位数的加法怎么办?

我们如何获取进位?下面的计算结果表示是否进位,0表示不进位,1表示进位

0 + 0 = 0
1 + 0 = 0
0 + 1 = 0
1 + 1 = 1
可以使用&来计算是否要进位
0 & 0 = 0
1 & 0 = 0
0 & 1 = 0
1 & 1 = 1

在位运算中使用<<表示左移来实现进位,所以进位就可以表示位

(x & y) << 1

于是我们就拥有了两个表达式

x ^ y 加法
(x & y) << 1 进位

所以在计算两个数的加法时,只需要判断是否要进位,如果要进位则执行进位操作后再执行加法和判断进位,知道不需要进位为止。

Java实现

public int getSum(int a, int b) {
    int jw = a & b;
    int jg = a ^ b;
    while (jw != 0){
        int t_a = jg;
        int t_b = jw << 1; // 进位
        jw = t_a & t_b;
        jg = t_a ^ t_b;
    }
    return jg;
}