原文：29. 两数相除(力扣 面试题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址：https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-029/

题目：

难度：Middle

相关话题：数学、二分查找

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

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

示例1:

输入: dividend = 10, divisor = 3
输出: 3

示例2:

输入: dividend = 7, divisor = -3
输出: -2

说明:

  • 被除数和除数均为 32 位有符号整数。

  • 除数不为0。

  • 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231− 1]。本题中，如果除法结果溢出，则返回 231− 1。

思路：

  • 使用减法，最直观的就是每次从被除数dividend中减去除数divisor，直到dividend<divisor，但是效率太低，因为数值是32位的数值，很容易TLE。

  • 使用叠加减法，和上面的思路差不多，但并不是每一次都只减去divisor，设定变量m，n分别为dividend还剩下的值，和当前被减的值。

    每一次都减去divisor*i，直到m<0，重置n，继续重复。

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {
  let negative=(dividend ^ divisor)<0,
      limit=Math.pow(2,31)

  if(dividend<divisor)return 0

  let res=0,count=0
  let n=0, m=dividend
  while(true){
    n+=divisor
    if(m-n>0){
      count+=1
      m=m-n
      res+=count
    }else {
      // 已经减到0了
      if(n===divisor){
        if(m-n===0)res++
        break
      }
      // 重置
      count=0
      n=0
    }
  }
  if(negative){
    return Math.max(-res,-limit)
  }else{
    return Math.min(res,limit-1)
  }
};

  • 使用位操作，位操作中>>相当于/2，<<相当于*2，因此对于dividend，找出一个idx，使得dividend>>idx后，刚好还比divisor大。

    这说明idx对应的除数是有效的，这个除数就是1<<idx，再将dividend减去当前除数divisor * ((1 << idx))，也就是(divisor << idx)。

    另外，由于js存在位溢出问题，因此在执行位运算时，计算绝对值let absBit=Math.abs((dividend >> idx))。

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {
  let negative=(dividend ^ divisor)<0,
      limit=Math.pow(2,31)
  dividend=Math.abs(dividend)
  divisor=Math.abs(divisor)
  if(dividend<divisor)return 0

  let res=0,idx=32
  while(idx>=0){
    // JS避免位溢出
    let absBit=Math.abs((dividend >> idx))
    if(absBit >= divisor){
      res+=(1 << idx)
      dividend-=(divisor << idx)
    }
    idx--
  }
  if(negative){
    return Math.max(-res,-limit)
  }else{
    return Math.min(res,limit-1)
  }
};