不用加减乘除做加法

[netty]

一. 十进制计算

计算十进制 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.计算进位，第 1 位相当于对两个数求与：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;
}

[reself]

论加法器的十八般武艺

[churchmice]

。。。
这就是加法器的硬件实现啊

最后硬件就是与门，或们和非门，能帮你实现所有组合逻辑，再加上寄存器，就是你现在用的芯片

[churchmice]

这个东西你去画下卡诺图就能推导出来了，请自行 Google

[Perry]

恭喜楼主喜提 ALU

[darksword21]

恭喜楼主喜提 ALU

[lance6716]

搞不懂模二加为啥被开除加法籍

[yujincheng08]

恭喜楼主喜提 ALU

[leoaqr]

恭喜楼主喜提 ALU

[deepreader]

村通网

[RtIHZ]

你先定义你所说的“加减乘除”里的“加”是什么意思

请问以下代码算实现了“加”吗？
if (op1 == 1 && op2 == 1) {
return 2;
}

[msg7086]

我以为现在上课是用的直播呢。

[slanternsw]

啥民科玩意儿，谔谔

[Mohanson]

半加器，全加器可以学一下的

[kZime]

在 v 站科普这个有点奇怪吧

[ynyounuo]

我还以为继去年 O(n log n) 后立马又有了更快的乘法算法

[Windsooon]

我想大多数人误会楼主了，楼主应该了解 ALU 以及 计算机硬件如何实现加法的，楼主的想法是如何在不使用加法符号来达到加法的目的，其实在不少算法题都会有这样的要求，例如 Leetcode 29 题，这类算法题主要考察的是对位运算的理解。我觉得楼主这个想法挺有趣的，而我之前也没有想到，感谢楼主的分享。

[ZhiyuanLin]

应该没读过计算机相关专业，学过数字电路不会觉得这是多神奇的事情。

[xieyudi2]

CPA, CSA, wallace tree...
虽然楼主是自己想出来的可嘉，但这个真的只是学校课本上的东西…

[wi]

可以的，不过这个书本上又讲

[pinktu]

你可以做一个加法器