1
package class033;
2

3
// 不用任何算术运算，只用位运算实现加减乘除
4
// 代码实现中你找不到任何一个算术运算符
5
// 测试链接 : https://leetcode.cn/problems/divide-two-integers/
6
public class BitOperationAddMinusMultiplyDivide {
7

8
  public static int MIN = Integer.MIN_VALUE;
9

10
  public static int divide(int a, int b) {
11
    if (a == MIN && b == MIN) {
12
      // a和b都是整数最小
13
      return 1;
14
    }
15
    if (a != MIN && b != MIN) {
16
      // a和b都不是整数最小，那么正常去除
17
      return div(a, b);
18
    }
19
    if (b == MIN) {
20
      // a不是整数最小，b是整数最小
21
      return 0;
22
    }
23
    // a是整数最小，b是-1，返回整数最大，因为题目里明确这么说了
24
    if (b == neg(1)) {
25
      return Integer.MAX_VALUE;
26
    }
27
    // a是整数最小，b不是整数最小，b也不是-1
28
    a = add(a, b > 0 ? b : neg(b));
29
    int ans = div(a, b);
30
    int offset = b > 0 ? neg(1) : 1;
31
    return add(ans, offset);
32
  }
33

34
  // 必须保证a和b都不是整数最小值，返回a除以b的结果
35
  public static int div(int a, int b) {
36
    int x = a < 0 ? neg(a) : a;
37
    int y = b < 0 ? neg(b) : b;
38
    int ans = 0;
39
    for (int i = 30; i >= 0; i = minus(i, 1)) {
40
      if ((x >> i) >= y) {
41
        ans |= (1 << i);
42
        x = minus(x, y << i);
43
      }
44
    }
45
    return a < 0 ^ b < 0 ? neg(ans) : ans;
46
  }
47

48
  public static int add(int a, int b) {
49
    int ans = a;
50
    while (b != 0) {
51
      // ans : a和b无进位相加的结果
52
      ans = a ^ b;
53
      // b : a和b相加时的进位信息
54
      b = (a & b) << 1;
55
      a = ans;
56
    }
57
    return ans;
58
  }
59

60
  public static int minus(int a, int b) {
61
    return add(a, neg(b));
62
  }
63

64
  public static int neg(int n) {
65
    return add(~n, 1);
66
  }
67

68
  // 这种乘法后面有大用处，尤其是求(a的b次方 % m)的结果，也叫龟速乘
69
  public static int multiply(int a, int b) {
70
    int ans = 0;
71
    while (b != 0) {
72
      if ((b & 1) != 0) {
73
        // 考察b当前最右的状态！
74
        ans = add(ans, a);
75
      }
76
      a <<= 1;
77
      b >>>= 1;
78
    }
79
    return ans;
80
  }
81

82
}