主题：算法 | 位运算实现乘除
目标：讲清楚两种算法；刻意练习：细致完整
目标读者：能看懂java代码的人
## 乘法
回归小学的笔算。
两个数
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··················
,
