divide two integers

2016-12-27

最近大脑越来越不听使唤,很多想法到嘴边了却突然忘了表达不出, 真要了老命, 忧伤30s… 都说好记性不如烂笔头,索性就重新拾起好久未动的blog, 无论是否对记忆有帮助, 起码记录下当前的自己。 Anyway, let’s start it.

问题

Divide two integers without using multiplication, division and mod operator. If it is overflow, return MAX_INT.

不用乘法、除法和取模算术符来计算两个整数的商

想法

乘除法其实是加减法的变种,理论上来说完全可以用加减法来代替乘除法来进行计算(不考虑时间复杂度), 因此我们可以用加减法来计算两个整数相除, 大概思路如下:

  • 加法 一直累加除数,直至其大于被除数,此时的循环次数即为所求的结果, 伪代码如下:

    tmp = divisor
    shift = 0
    while dividend >= tmp
    tmp += divisor
    shift++
  • 减法 一直递减被除数,直至其小于除数,此时的循环次数即为所求的结果, 伪代码如下:

    tmp = dividend
    shift = 0
    while tmp >= divisor
    tmp -= divisor
    shift++

上述的加减法的确能够解决问题,并且在一些情况下效率还蛮高,但在一些极端的情况下时间复杂度却为O(n), 因此我们需要想办法提高收敛速度,减少循环次数降低时间复杂度。在乘法和除法被限制使用的情况下,我们 只能放出大杀器移位操作(左移一位相当于乘以2, 右移一位相当于除以2)。 另外在数学上,任何一个整数n都可以表示成n = a0*2^0 + a1*2^1 + ... + an*2^n, 间接说明了移位操作的可行性。

算法

描述

  1. 初始化变量result
  2. 如果被除数dividend大于等于除数divisor, 执行3, 否则执行6
  3. 初始化临时变量shift
  4. 被除数左移位至dividend < (divisor << shift), 然后让dividend等于dividend - (divisor << (shift -1))
  5. 让result加上左移的值, 跳转到2继续执行
  6. 输出result

codes

  • golang:
    func divide(dividend int, divisor int) int {
    if divisor == 0 {
    return math.MaxInt64
    }
    if dividend == 0 {
    return 0
    }

    sign := 1
    if (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0) {
    sign = -1
    }
    if dividend < 0 {
    dividend = -dividend
    }
    if divisor < 0 {
    divisor = -divisor
    }

    var result int
    for dividend >= divisor {
    var shift uint
    for dividend >= divisor<<shift {
    shift++
    }
    dividend -= divisor << (shift - 1)
    result += 1 << (shift - 1)
    }

    if sign == -1 {
    return -result
    }
    return result
    }

Q&A

写的比较仓促,如有错误或者未考虑到的问题,欢迎指出😊