位运算实现加减乘除
前提：位运算实现加减乘除，过程中不能出现任何算数运算符。
加法
利用每一步无进位相加的结果+进位的结果不停计算，直到进位消失。
1
2
3
4
5
6
7
8
9
int add(int a, int b){
int ans = a; // a和b无进位相加的结果
while(b != 0){ // 进位信息不为0时循环
ans = a ^ b;
b = (a & b) << 1; // a和b相加时的进位信息
a = ans;
}
return ans;
}
减法
利用加法，和一个数字x相反数就是(~x) + 1（按位取反后加一）。
1
2
3
int subtract(int a, int b){
return add(a, add(~b, 1));
}
乘法
回想小学时候怎么学的乘法，除此以外没别的了。
1
2
3
4
5
6
7
8
9
10
11
12
int multiply(int a, int b) {
int ans = 0;
unsigned int u_b = b; // 转为无符号处理右移
while (u_b != 0) {
if (u_b & 1) {
ans = add(ans, a);
}
a <<= 1;
u_b >>= 1; // 无符号右移(自动补零)
}
return ans;
}
除法
为了防止溢出，让被除数右移，而不是除数左移。从高位尝试到低位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 必须保证a和b都不为整数最小值
int div(int a, int b) {
// 使用无符号处理绝对值
unsigned int x = a < 0 ? (unsigned int)(~a) + 1 : a;
unsigned int y = b < 0 ? (unsigned int)(~b) + 1 : b;
int ans = 0;
// 从31位开始检测
for(int i = 31; i >= 0; i = subtract(i, 1)) {
if((x >> i) >= y) {
ans |= (1 << i);
x = subtract(x, y << i);
}
}
return (a < 0) ^ (b < 0) ? -ans : ans;
}
int divide(int a, int b){
if(a == INT_MIN && b == INT_MIN){
return 1;
}
if(a != INT_MIN && b != INT_MIN){
return div(a, b);
}
if(b == INT_MIN){
return 0;
}
if(b == -1){ // a是整数最小，b是-1，返回INT_MAX，题目明确这么说了
return INT_MAX;
}
a = add(a, b > 0 ? b : -b);
int ans = div(a, b);
int offset = b > 0 ? -1 : 1;
return add(ans, offset);
}
