题目名称

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例

输入: dividend = 10, divisor = 3

输出: 3

解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

题解

下面是一位大佬的题解，参照题解和一些边界用例才把题解答出来

解题思路：这题是除法，所以先普及下除法术语

商，公式是：(被除数-余数)÷除数=商，记作：被除数÷除数=商…余数，是一种数学术语。
在一个除法算式里，被除数、余数、除数和商的关系为：(被除数-余数)÷除数=商，记作：被除数÷除数=商…余数，

进而推导得出：商×除数+余数=被除数。

要求商，我们首先想到的是减法，能被减多少次，那么商就为多少，但是明显减法的效率太低
那么我们可以用位移法，因为计算机在做位移时效率特别高，向左移1相当于乘以2，向右位移1相当于除以2

我们可以把一个dividend（被除数）先除以2^n，n最初为31，不断减小n去试探,当某个n满足dividend/2^n>=divisor时，

表示我们找到了一个足够大的数，这个数*divisor是不大于dividend的，所以我们就可以减去2^n个divisor，以此类推

我们可以以100/3为例

2^n是1，2，4，8…2^31这种数，当n为31时，这个数特别大，100/2^n是一个很小的数，肯定是小于3的，所以循环下来，

当n=5时，100/32=3, 刚好是大于等于3的，这时我们将100-32*3=4，也就是减去了32个3，接下来我们再处理4，同样手法可以再减去一个3

所以一共是减去了33个3，所以商就是33

这其中得处理一些特殊的数，比如divisor是不能为0的，Integer.MIN_VALUE和Integer.MAX_VALUE

答案

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
/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {
    if(dividend === 0) return 0
    let flag = 1
    if((dividend >= 0 && divisor >= 0) || (dividend < 0 && divisor < 0)) {
        flag = 1
    } else {
        flag = -1
    }
    dividend = Math.abs(dividend)
    divisor = Math.abs(divisor)
    if(dividend < divisor) return 0
    let pow = 0, res = 0
    while(pow <= 32) {
        if(dividend / Math.pow(2, pow) < divisor) {
            res += Math.pow(2, pow - 1)
            dividend -= Math.pow(2, pow - 1) * divisor
            if(dividend < divisor) break;
            pow = 0
        } else {
            pow++
        }
    }
    if(flag > 0) {
        return res > Math.pow(2, 31) - 1 ? Math.pow(2, 31) - 1 : res
    }
    if (flag < 0) {
        return res > Math.pow(2, 31) ? Math.pow(2, 31) - 1 : -res
    }
};