位运算实现加减法

原标题：位运算实现加减法

主题：位运算实现加减法

目标：讲清楚两种算法的实现；刻意练习：教程，细致完整

目标读者：了解基本位运算，并能读懂java代码的人

# 位运算实现加减乘除

计算机底层的加减乘除就是由位运算实现的。

理解它们，可以帮助我们更好的理解特有的现象，比如为什么整形除以整形的结果也是整形。

今天时间有限，只能先来加减了。

## 加法

异或运算，相当于无进位相加。

0^1=1，0+1=1

0^0=0，0+0=0

1^1=0，1+1=2，二要进一，所以是10，原位置上还是0，就相当于把进位信息给抹去了。

既然进位信息被抹去了，就要想办法把进位信息加回来。

0101

0011

&

0001

两个数字与运算，得到的结果相当于记录了进位信息，因为只有两个数字都是1的时候，结果才是1。也只有两个数字都是1的时候，相加才用进位。

但进位信息的位置不对，要往前移一位，也就是左移。

所以，进位信息的最终结果为：0001<<1=0010。

把无进位相加的结果加上进位信息，就是最终加法的结果。

而且，当进位信息为0的时候，无进位相加^0=进位相加。

所以，我们的目标就是一直重复上面的操作，直到进位信息变成0。

我们拿上面的两个数当例子。

一、异或

0101

0011

^

0110

二、与运算，并左移一位

上面算过了，结果是

0010

三、一二步结果，异或

0110

0010

^

0100

四、一二步结果，与运算，并左移一位

0110

0010

&

0010

<<1

0100

五、三四步结果，异或

0100

0100

^

0000

六、三四步结果，与运算，并左移一位

0100

0100

&

0100

<<1

1000

七、五六步结果，异或

0000

1000

^

1000

八、五六步结果，与运算，并左移一位

0000

1000

&

0000

<<1

0000

好，这时候，进位信息为零了。那第七步的结果就是结果。

不放心的话，还可以再拿第七步和第八步的结果再异或一下。

1000

0000

^

1000

按照之前的推理，无进位相加^0=进位相加。

即a^0=a+0，所以，任何数和零异或都会等于它本身。

验算一下结果，确实是没错的。

0101（5）

0011（3）

+

1000（8）

接下来上代码：

```java

public static int add(int a, int b) {

int result = 0;

while (b != 0) {

result = a ^ b;

b = (a & b) << 1;

a = result;

}

return result;

}

```

## 减法

a+b=a+(-b)，所以减法可以延用加法的逻辑。

只需要多取一个相反数就好了。

相反数的位运算为，取反+1。

上代码

```java

public static int oppositeNumber(int num) {

return add(~num, 1);

}

public static int minus(int a, int b) {

return add(a, oppositeNumber(b));

}

```

字数：不统计

耗时：1小时30分

··················END··················