不使用除法运算符的情况下获取商

今天在力扣看到一题，就如题目所说，不用除法实现除法功能。

我当然不会了，除了能想到要用二进制运算符外，没有一点思路，便问了AI。

思路就是，不断找小于被除数的，除数的最大2的幂数。

比如 10/3 因为使用二进制运算符，那么首先来找3乘以2的幂数。

比如3 的二进制为 0011 进行左移1位后，变成 0110 十进制为6，继续左移则变成了12

  • 3乘以2的0次幂 3
  • 3乘以2的1次幂 6
  • 3乘以2的2次幂 12

而12大于了被除数10，所以我们只取2的一次幂，从2的第0次幂开始，总共进行两次运算得到的6，所以我们先记下已经运算了 2次 。

之后，将被除数减去我们计算的刚才的结果6 那么剩余4。

然后继续从头开始计算，发现只有乘以2的0次幂小于4，也就是只有一次，所以继续加上刚才的结果，最终结果为3

public static int df(int a, int b) {
    int count = 0;
    int less = a;
    while (less >= b) {
        int currentCount = 0;
        for (int i = 0; i <= 31; i++) {
            if (b << i > less) {
                less -= b << (i - 1);
                break;
            } else {
                currentCount = 1 << i;
            }
        }
        count += currentCount;
    }
    return count;
}

这里有一点需要解释的就是，currentCount = 1 << i

比如10/3，当循环第二次时，这个b<<(i-1)的值是6，也就是两个3，所以需要获取：

  • i为1时，就是10减去一个3，那么i应该为1，意思是减去了一次
  • i为2时，就是10减去两个3，那么i应该为2，意思是减去两次
  • i为3时，就是10减去三个3，那么i应该为4，意思是减去四次
  • i为4时，就是10减去四个3，那么i应该为8，意思是减去八次

依次类推。

我去，写完后我又想到个更简单的，简单到不用解释

public static int a(int a, int b) {
    int temp = 0;
    int count = 0;
    while (temp < a) {
        temp += b;
        count++;
    }
    if (temp > a) {
        count--;
    }
    return count;
}

面试可别这么写，容易被人乱棍打出来。