算法 | 位运算实现乘除

## 乘法

回归小学的笔算。

两个数

0101(5)

0110(6)

可以像小学学十进制乘法那样相乘。

文字不太好描述了，我就直接动手画了（不要嫌我的字丑）。

其中蓝色的部分为补的零。

最终的结果是没错的：

1110(30)

然后，我们再用文字的方式来描述一遍。

两个数A、B相乘。

从B的最低位开始，

如果当前位是0，则结果为0；

如果最低位是1，则结果为A。

从第二开始，结果就需要补零了，也就是需要左移一位。

最后将每一位的结果相加。

至于怎么得到B相应位置是1还是0呢？

可以使用和1做与运算的方式。

结果为0，则当前位为0；

结果非0，则当前位为1。

算完之后，再通过位运算来切换当前位。

我刚想了一下，原本觉得让1左移也可以，但1左移不好判断结束的时间点。只能一直左移到32位，整个int结束，会增加一些不必要的计算。

所以，得使用B右移的方式，当B=0了，就可以结束了。

上代码：

```java

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

int result = 0;

while (b != 0) {

if ((b & 1) != 0) {

//result += a;

result = add(result, a);

}

a <<= 1;

b >>>= 1;

}

return result;

}

```

## 除法

除法，四则运算里最麻烦的一个。

但，依旧可以回归小学的笔算。

两个数：

11011(27)

11(3)

其中黑色的为补齐内容，虽然我们通常笔算的时候不会写出来。

其中蓝色的地方为补零，依旧是左移的操作。

最终结果也没错：

1001(9)

翻译一下上面的运算。

11011为A

11为B

先将B左移N位，移到最大的可能性，但不能比A大。

这时候，结果在1左移N位的位置为1。

A减去B左移N位的值。

继续上述步骤，

B左移N-1位，如果比A大

结果在1左移N-1的位置为0。

如果相遇等于A，则同上。

直到N=0，流程结束。

但在实际写代码的时候，要做一些调整，因为左移可能会涉及到左移到符号位，导致不可预知错误的问题。

所以，可以使用A的右移来代替。

这样做，只是为了确定N，所以两个是可以互换的。

如下图所示，写了一个不正规的除法。

蓝色的部分，代表这些数字因为位移的关系被省略掉了。

比如：0001右移一位，就会变成0000,1就没了。

最后，把某位的值改为1，可以用或运算。

例：

10001

想把第三位的位置改成1。

就可以

10001

00100(1<<2)

^

10101

上代码：（我还是用常规的加减乘吧，不用自己实现的了，不然代码看起来要复杂一些）

```java

//判断是否为负数

public static boolean isNegativeNumber(int num) {

return num < 0;

}

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

//需要都先转换成正数

int tempA = isNegativeNumber(a) ? -a : a;

int tempB = isNegativeNumber(b) ? -b : b;

int result = 0;

for (int i = 30; i >= 0; i--) {

if ((tempA >> i) >= tempB) {

tempA -= (tempB << i);

result |= (1 << i);

}

}

//如果符号相反，则返回负数，如果否则返回正数

//异或，相等返回0（false），不相等返回1（true）

//相当于 isNegativeNumber(a) != isNegativeNumber(b)

return isNegativeNumber(a) ^ isNegativeNumber(b) ? -result : result;

}

```

到这里其实还没有完，还有一种特殊情况要讨论，那就是系统最小值是取不了相反数的。

在java中int的取值范围是-2^31~2^31-1。

所以int是装不下2^31的。

所以要分情况讨论：

a为最小值，b为最小值：结果为1；

a不为最小值，b为最小是：结果为0；

a为最小值，b不为最小值：

①b为-1：

理论上应该返回系统最大值+1，但那样就要返回long类型了。所以给它返回系统最大值，虽然是错的。

②b不为-1：

（a+1）/b=c

a-(b\*c)=d

d/b=e

result=c+e

a不为最小值，b不为最小值：

上面的方法。

上代码：

```java

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

if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {

return 1;

} else if (b == Integer.MIN_VALUE) {

return 0;

} else if (a == Integer.MIN_VALUE) {

if (b == -1) {

return Integer.MAX_VALUE;

} else {

//（a+1）/b=c

//a-(b*c)=d

//d/b=e

//result=c+e

int c = (a + 1) / b;

int d = a - (b * c);

int e = d / b;

return c + e;

}

} else {

return div(a, b);

}

}

```

字数：不统计

耗时：4小时

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