题目链接: leetcode-29-两数相除
此题需要在不使用乘法，除法，取模的情况下求的两数相除的结果, 开始看到这道题，以为使用位运算做的，结果发现位运算里面太多的循环，导致并不能通过测试.
首先要知道除法的定义, 除法的定义其实非常简单，比如: 10 / 3 = x => 3x = 10 => x + x + x = 10 所以我们只需要循环执行 +除数 操作，直到和大于或者小于被除数时，就可以得到当前的商。当然使用减法也是可以的。 这就是暴力求解的做法
但是单纯的循环执行 +除数 操作非常耗时，所以需要对步长进行调整，每一次相加如果小于被除数，那么就将步长加一，如果大于被除数了就调整步长为 0 再次重复上述操作，直到相加结果大于被除数，并且步长为0.
比如 16 / 3 第一次 +3, 第二次 +6，第三次 +12 因为第三次的结果已经大于 16 了所以我们需要调整为步长，第四次 +3，第五次 +6 因为第五次又超过了被除数，所以再次调整步长，第六次 +3 第七次 +6 又超过了被除数，再次调整步长 第八次 +3 依旧超过了被除数，并且步长为 0 所以直接返回商.
直接看代码:
export default function divide(dividend: number, divisor: number): number {
// 一系列剪枝操作
// 除数与被除数相等时直接 返回 1
if (dividend === divisor) return 1;
// 除数为 1 时直接返回除数
if (divisor === 1) return dividend;
// 除数为 -1 时，如果被除数为 2^31 那么溢出了，所以直接返回 2^31 - 1，否则就返回被除数取反
if (divisor === -1) {
if (dividend === -2147483648) return 2147483647;
return ~dividend + 1;
}
// *统一两个数的符号
const _dividend = dividend < 0 ? ~dividend + 1 : dividend;
const _divisor = divisor < 0 ? ~divisor + 1 : divisor;
// 除数大于被除数返回 0
if(_divisor > _dividend) return 0;
// 用于存储当前的和
let sum = 0;
// 商
let quotient = 0;
// 步长
let step = 0;
// *注意在 js 中 number 因为包含了浮点数，只剩下了 32 位，然后还有一位符号位，所以整数部分只有 31 位，所以步长不能溢出，这里就是确定最大步长 31 减去当前除数的位数就是最大步长
const stepMax = 31 - _divisor.toString(2).length;
while (1) {
// *首先计算出当前 加数
const tempDivisor = _divisor << step;
// 如果 和 大于被除数
if ((sum + tempDivisor) > _dividend) {
// 如果步长为 0 那么直接返回
if (step === 0) break;
// 否则将步长重置为 0，并且跳过这次循环
step = 0;
continue;
}
// sum 存储和
sum += tempDivisor;
// !quotient 应该存储当前相加的 _divisor 的个数，那么就应该是 (_divisor << step) / _divisor 所以得到 1 << step
quotient += 1 << step;
// *确保 step
测试结果:
Original: https://www.cnblogs.com/99xx/p/divide-two-integers.html
Author: 99xx
Title: leetcode算法-两数相除 前端
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/643206/
转载文章受原作者版权保护。转载请注明原作者出处！