不用加减乘除做加法

一. 十进制计算

计算十进制 13+9:

1.计算不进位的和。十位 1 不变,个位 3 加 9 等于 2,结果为 12 ;

2.计算进位。十位没进位,个位进位为 1,结果为 10。

再计算十进制 12+10:

1.计算不进位的和。十位 1 加 1 等于 2,个位 2 加 0 等于 2,结果为 22 ;

2.计算进位。十位没进位,个位也没进位,结果为 0。

因此结果 13+9=22。

二. 二进制计算

13 二进制为:1101,9 二进制为:1001。

十进制是遇到大于等于 10 就保留余数,然后进位 1。

那对应到二进制,就是遇到 2 就保留余数 0,然后进位 1。(二进制位之和不可能大于 2 )

计算二进制 1101+1001:

1.计算不进位的和。从左到右,第 1 位为 0,第 2 位为 1,第 3 位为 0,第 4 位为 0,结果为 0100 ;

2.计算进位。从左到右,第 1 位进位 1,第 2、3 位没有进位,第 4 位进位 1,结果为 1001。不对,进位右边要补 0,正确结果是 10010。

计算二进制 0100+10010:

1.计算不进位的和:10110 ;

2.计算进位:无。

因此结果为 10110=22。

三.二进制加法公式

1.分析上面对二进制的计算过程,不难发现:
1)计算不进位的和,相当于对两个数进制异或:1101^1001=0100 ;

2)计算进位,相当于对两个数求与:1101&1001=1001,然后再对其进行左移 1 位:1001<<1=10010。 然后再重复以上两个步骤。这里再异或一次就得到结果了,没进位:0100^10010=10110=22。

2.计算 a+b,等价于(a^b)+((a&b)<<1)。
由于公式中又出现了+号,因此要再重复 2 )这个等价的计算过程。

结束条件是:没有进位了。

如果不明白,看一下前一点 1 )。

/**
 * 二进制求和.
 * 
 * @param a
 * @param b
 * @return
 */
public int add(int a, int b) {
    while (b != 0) {
        int plus = (a ^ b); // 求和(不计进位). 相同位置 0,相反位置 1
        b = ((a & b) << 1); // 计算进位. 先保留同为 1 的位,都为 1 的位要向左进位,因此左移 1 位
        a = plus;
    }
    return a;
}

核心思想是,不断做等价转换,直到没有进位,加法自然就消失了。


---转载本站文章请注明作者和出处 二进制之路(binarylife.icu),请勿用于任何商业用途---

留下评论