LeetCode: Divide Two Integers

题目

https://oj.leetcode.com/problems/divide-two-integers/

分析

  1. 题目要求实现除法运算且不能用乘除和取余运算, 一开始想用的递减计数的方式, 显然这种方法效率太低了, 从而导致超时。

不能用乘除和取余如何快速的逼近结果呢? 答案是采用移位运算, 以指数的形式增长, 快速逼近最终的结果。

举例来说明, 137 / 7 = 19如何用移位运算来快速得到最终结果呢?

           135 - 7 × 2 ^ 4 = 23    > 7

           23   - 7 * 2 ^ 1  = 9      > 7

           9     - 7 * 2 ^ 0  = 2      <  7    停止运算

最终结果    24 + 21 + 20 = 19

  1.  为了防止溢出, 将int型参数隐式转换为long long型参数。

代码

class Solution
{
public:
    int divide(long long dividend, long long divisor)
    {
        int res = 0;
        int sign = (dividend>0 && divisor>0) || (dividend<0 && divisor<0);
        dividend = dividend > 0 ? dividend : -dividend;
        divisor = divisor > 0 ? divisor : -divisor;

        while (dividend >= divisor)
        {
            long long res_temp = 1;
            while (res_temp * divisor <= dividend)
                res_temp <<= 1;
            res_temp >>= 1;
            res += res_temp;
            dividend -= res_temp * divisor;
        }
        return sign ? res : -res;
    }
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39558059