Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
一、原理
1、化简
先看一个例子：
看一下 3 + 4 的加法运算
3 的二进制表示： 011
4 的二进制表示： 100
3^4 (3按位异或4)的结果是： 111 => 7
上面的到的结果是就是 3 + 4 的实际结果
再看一个例子：
12 的二级制表示: 01100
19 的二进制表示: 10011
12^19 的结果是： 11111 => 31
再看一个例子：
13 的二进制表示：01101
19 的二进制表示：10011
13^19 的结果是： 11110 => 20
通过上面的三个例子不难发现: 当二进制数的每一位加法中不发生进位时，按位异或的结果就是最终的加法结果，那么我需要做的就是将所有的加法操作最终都简化成没有进位的加法操作，最终的结果就是两个数按位异或的结果。
2、怎么处理有进位的加法？
拆分
将两个数的加法拆分为 进位加法和不进位加法
看一个例子：
编号：1 2 3 4 5
————————
1 0 0 1 1 => 19
+ 1 1 0 1 0 => 26
————————–
先求只有不进位的两个位相加的值，编号为2、3、5这三位的加法不发生进位操作，需要进位的相加位数直接按照结果为0处理，得到的结果为
编号：1 2 3 4 5
————————
1 0 0 1 1
+ 1 1 0 1 0
————————
不进位： 0 1 0 0 1
进位两个位相加的值，编号为1、4这三位的加法会发生进位操作，不需要进位的直接按照结果0处理，得到的结果为：
编号：1 2 3 4 5
————————
1 0 0 1 1
+ 1 1 0 1 0
————————
不进位： 0 1 0 0 1
进 位： 1 0 0 1 0 0
再将两个结果按位异或：
不进位：0 0 1 0 0 1
进 位：1 0 0 1 0 0
————————
1 0 1 1 0 1 => 45
由此可见可以将一个二进制加法拆分为有进位的位数相加结果 和 无进位的位数相加的结果最终按位异或
3、递归
再看一个例子
编号：1 2 3 4 5
————————
1 0 1 1 1 => 23
+ 1 1 0 1 1 => 27
————————
不进位： 0 1 1 0 0 => 12
进 位： 1 0 0 1 1 0 => 38
通过一次相加得到的结果不能完全实现化简操作，所以需要递归地进行化简操作
编号：1 2 3 4 5
————————
1 0 1 1 1 => 23
+ 1 1 0 1 1 => 27
————————
不进位： 0 0 1 1 0 0 => 12
进 位：1 0 0 1 1 0 => 38
————————
不进位：1 0 1 0 1 0 => 42
进 位：0 0 1 0 0 0 => 8
————————
不进位：1 0 0 0 1 0 => 34
进 位：0 1 0 0 0 0 => 16
————————
不进位：1 1 0 0 1 0 => 50
进 位：0 0 0 0 0 0 => 0
以上实例通过递归的方式可以得到最终的结果
二、位运算实现
通过以上几个实例我们明白了如何通过二进制的几个步骤来实现任意整数的加法操作，现在我们需要把这件事情用位运算进行表示。
位运算表示不进位加法：
不进位加法其实就是一个异或操作
位运算表示进位加法：
进位加法其实就是一个与操作的结果左移一位
三、代码实现
js实现：
function sum (a, b) { if (b===0) return a; return sum(a^b, (a&b)<<1) }
java实现：
public int sum(int a, int b) { if (b==0) return a; return sum(a^b, (a&b)<<1); }
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/168378.html原文链接：https://javaforall.net
