原题地址：两数相除
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
说明:
- 被除数和除数均为 32 位有符号整数。
- 除数不为 0。
- 假设我们的环境只能存储 32 位有符号整数，其数值范围是 $-2^{31}$, $2^{31}-1$。本题中，如果除法结果溢出，则返回$2^{31}-1$。
除法转为减法
当被除数大于等于除数时，被除数就减去除数，然后商就加一，一直循环直到被除数小于除数时就可以得到结果：
/**
* @param {number} dividend
* @param {number} divisor
* @return {number}
*/
const divide1 = function(dividend, divisor) {
// 由于负数的存储范围比正数大1，所以最小的负数除以-1时就会溢出
if (dividend === -0x80000000 && divisor === -1) {
return 0x7fffffff
}
let isNegative = (dividend ^ divisor) < 0; // 记录符号
// 都转为正数
dividend = Math.abs(dividend); //
divisor = Math.abs(divisor);
// 转为减法运算并记录运算次数
let count = 0;
while (dividend >= divisor) {
dividend -= divisor;
count ++;
}
return isNegative ? -count : count;
};
测试：
let start = new Date();
const test = divide1;
console.log(test(10, 3)); // 3
console.log(test(7, -3)); // -2
console.log(new Date().getTime() - start.getTime()); // 5
时间复杂度： 时间复杂度为O(n)，n就是被除数除以除数得到的商
空间复杂度： 常数级空间复杂度O(1)
位移运算
上述算法的运行效率相当低，特别时当被除数绝对值特别大而除数绝对值又特别小的时候，所以该算法提交到LeetCode时会超时。
题目要求我们不能使用乘法和除法操作，但我们可以用位移运算来代替乘法和除法操作。我们可以先把$dividend$除以$2^i$，$i$从$31$开始依次减小，直到我们找到一个数$i$，使得 $dividend\div2^i\geq divisor$，证明我们找到了一个足够大的数$i$，使得 $2^i \times divisor \leq dividend$。然后我们就可以让 $dividend$ 减去这个数，并对剩下的数继续同样的操作。例如我们以$100 \div 3$为例，我们从$31$开始尝试，发现能找到的最大的符合条件的$i$为$5$，$100 \div 2^5 = 100 \div 32 = 3$，刚好满足大于等于$3$的条件，$100 - 2^5 \times 3 = 4$，即$100$减去了$32$个$3$，然后我们对$4$进行同样的操作，可以再减去一个$3$，总共减去了$33$个$3$，所以最终的结果为$33$。
具体实现如下：
/**
* @param {number} dividend
* @param {number} divisor
* @return {number}
*/
const divide2 = function(dividend, divisor) {
// 由于负数的存储范围比正数大1，所以最小的负数除以-1时就会溢出
if (dividend === -0x80000000 && divisor === -1) {
return 0x7fffffff
}
let isNegative = (dividend ^ divisor) < 0; // 记录符号
// 都转为正数
dividend = Math.abs(dividend);
divisor = Math.abs(divisor);
let result = 0;
for (let i = 32; i >= 0; i --) {
if ((dividend>>>i) >= divisor) { // dividend/2^i >= divisor，注意使用无符号位移
result += (1<<i); // result += 2^i
dividend -= (divisor<<i); // dividend -= divisor * 2^i
}
}
return isNegative ? -result : result;
};
测试：
let start = new Date();
const test = divide2;
console.log(test(10, 3)); // 3
console.log(test(7, -3)); // -2
console.log(test(-2147483649, 1)); // -2147483649
console.log(new Date().getTime() - start.getTime()); // 8
时间复杂度： 最多只需要32次循环，所以时间复杂度为常数级，$O(1)$
空间复杂度： 常数级额外空间，空间复杂度为$O(1)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 2,2019