29. Divide Two Integers

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Note:

• Both dividend and divisor will be 32-bit signed integers.
• The divisor will never be 0.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [?2³¹, 2³¹ ? 1]. For the purpose of this problem, assume that your function returns 231 ? 1 when the division result overflows.

簡單來說就是不用‘乘法’皇耗、‘除法’和‘取余’運算來求兩個整數(shù)的商例嘱，注意結(jié)果要在 [?2³¹, 2³¹ ? 1]

Round One

• 暴力減法(如下)，我賭5毛，超時（Time Limit Exceeded）蹋笼！

// Swift Code
class Solution {
    func divide(_ dividend: Int, _ divisor: Int) -> Int {
        let sign = (dividend >= 0) == (divisor > 0) ? 1 : -1
        var dividend = abs(dividend)
        let divisor = abs(divisor)
        var result = 0
        while dividend > divisor {
            dividend -= divisor
            result += 1
        }
        if dividend == divisor {
            result += 1
        }
        return sign < 0 ? -result : result
    }
}

Round Two

一個一個減肯定是超時了星持，要是一批一批減呢摩幔？
所以就需要先成倍放大被除數(shù)藻茂，不允許用‘乘法’、‘除法’和‘取余’ 還有 ‘<<’裳食、‘>>’

// Swift Code
class Solution {
    func divide(_ dividend: Int, _ divisor: Int) -> Int {
        // 除數(shù)矛市、被除數(shù)符號不一致時候商為負數(shù)
        let sign = (dividend >= 0) == (divisor > 0) ? 1 : -1

        // 擴大下數(shù)據(jù)類型，避免溢出
        var _dividend = Int64(abs(dividend))
        let _divisor = Int64(abs(divisor))

        var result = 0
        var temp = 1
        var _divisor_temp = _divisor

        // 放大被除數(shù)
        while _divisor_temp < _dividend {
            _divisor_temp = _divisor_temp << 1
            temp = temp << 1
        }

        // 在合理范圍內(nèi)縮小被放大的被除數(shù)
        while _divisor_temp > 0, _divisor_temp > _divisor {
            while _divisor_temp > _dividend {
                _divisor_temp = _divisor_temp >> 1
                temp = temp >> 1
            }
            _dividend -= _divisor_temp
            result += temp
        }

        // 竟然一樣大诲祸，所以再來一次了
        if _dividend == _divisor {
            result += 1
        }

        // 結(jié)果是有范圍限制的
        return sign < 0 ? max(-result, Int(Int32.min)) : min(result, Int(Int32.max))
    }
}

TestCase

// Swift Code
assert(Solution().divide(10, 3) == 3)
assert(Solution().divide(3, 3) == 1)
assert(Solution().divide(1, 1) == 1)
assert(Solution().divide(2, 3) == 0)
assert(Solution().divide(7, -3) == -2)
assert(Solution().divide(-2147483648, -1) == 2147483647)
assert(Solution().divide(0, 2147483648) == 0)