位运算实现整数加减乘除运算

两数相除本文借这道题，分析如何用位运算实现一套完整的整数运算体系。

1. 加法运算

1
2
3
4
5
6
7
8
9


public static int add(int a, int b) {
    int ans = a;
    while (b != 0) {
        ans = a ^ b;        // 无进位相加
        b = (a & b) << 1;   // 计算进位
        a = ans;
    }
    return ans;
}

2. 取反运算

1
2
3


public static int neg(int n) {
    return add(~n, 1);
}

经典的补码取反公式:一个数的相反数等于按位取反加1。

3. 减法运算

1
2
3


public static int minus(int a, int b) {
    return add(a, neg(b));
}

4.乘法运算

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


public static int multiply(int a, int b) {
    int ans = 0;
    while (b != 0) {
        if ((b & 1) != 0) {
            ans = add(ans, a);
        }
        a <<= 1;
        b >>>= 1;
    }
    return ans;
}

思路

将乘法转化为加法和移位操作,本质是将b的二进制展开:

1
2


a × b = a × (b₀×2⁰ + b₁×2¹ + b₂×2² + ...)
      = a×b₀ + (a<<1)×b₁ + (a<<2)×b₂ + ...

每次检查b的最低位,如果为1则累加当前的a,然后a左移(相当于×2),b右移(处理下一位)。

5.除法运算

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


public static int divide(int a, int b) {
    if (a == MIN && b == MIN) {
        return 1;  // 最小值除以最小值 = 1
    }
    if (a != MIN && b != MIN) {
        return div(a, b);  // 都不是最小值,正常处理
    }
    if (b == MIN) {
        return 0;  // 任何非最小值除以最小值 = 0
    }
    if (b == neg(1)) {
        return Integer.MAX_VALUE;  // 题目要求溢出返回最大值
    }
    
    // a是最小值,b不是最小值也不是-1
    a = add(a, b > 0 ? b : neg(b));
    int ans = div(a, b);
    int offset = b > 0 ? neg(1) : 1;
    return add(ans, offset);
}

思路

当a是最小值时:

先将a向0的方向移动|b|个单位:a = a + |b|
对调整后的a进行除法:ans = div(a, b)
补偿之前的调整:
- 如果b > 0:商应该减1(因为我们让被除数变大了)
- 如果b < 0:商应该加1(因为负数除法的特性)

函数:div

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


public static int div(int a, int b) {
    int x = a < 0 ? neg(a) : a;  // 转为正数
    int y = b < 0 ? neg(b) : b;
    int ans = 0;
    
    for (int i = 30; i >= 0; i = minus(i, 1)) {
        if ((x >> i) >= y) {
            ans |= (1 << i);
            x = minus(x, y << i);
        }
    }
    
    return a < 0 ^ b < 0 ? neg(ans) : ans;
}

思路

类似于二分查找,从高位到低位试探商的每一位:

将x和y都转为正数
从第30位开始(第31位是符号位)向下遍历
检查x >> i是否大于等于y:
- 如果是,说明商的第i位是1,同时从x中减去y << i
最后根据符号决定结果的正负