29.两数相除

链接：29.两数相除
难度：Medium
标签：位运算、数学
简介：给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

题解 1 - typescript

• 编辑时间：2021-10-12
• 执行用时：80ms
• 内存消耗：39.8MB
• 编程语言：typescript
• 解法介绍：不符合题意，直接利用乘法除法计算。

function divide(dividend: number, divisor: number): number {
  const num =
    Math.floor(Math.abs(dividend) / Math.abs(divisor)) * (divisor * dividend >= 0 ? 1 : -1);
  return num >= (-2) ** 31 && num <= 2 ** 31 - 1 ? num : 2 ** 31 - 1;
}

题解 2 - typescript

• 编辑时间：2021-10-12
• 执行用时：92ms
• 内存消耗：39.7MB
• 编程语言：typescript
• 解法介绍：利用^判断正负号，利用 num << i === num * 2 << i 来取值。

function divide(dividend: number, divisor: number): number {
  if (dividend === (-2) ** 31 && divisor === -1) return 2 ** 31 - 1;
  if (dividend === (-2) ** 31 && divisor === 1) return dividend;
  const flag = (dividend ^ divisor) < 0 ? -1 : 1;
  dividend = Math.abs(dividend);
  divisor = Math.abs(divisor);
  let ans = 0;
  for (let i = 31; i >= 0; i--) {
    if (dividend >>> i >= divisor) {
      ans += 1 << i;
      dividend -= divisor << i;
    }
  }
  return flag * ans;
}