LeetCode 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  

思路

还是要善于运用bit manipulation, 把divisor每次左移一位相当于乘以2,当大于dividend之后则找到了一个边界, 相减之后可以继续按这种方法做。 参考Youtube

Swift 题解

func divide(_ dividend: Int, _ divisor: Int) -> Int {  
        if dividend == Int32.min {
            if divisor == -1 {
                return Int(Int32.max)
            } else if divisor == 1 {
                return dividend
            }
        }

        var divd = dividend
        var divs = divisor

        var sign = 1
        if dividend < 0 {
            divd = 0 - divd
            sign *= -1
        }

        if divisor < 0 {
            divs = 0 - divs
            sign *= -1
        }

        var result = 0

        while divd >= divs {
            var shift = 0
            while (divd >= (divs << shift)) {
                shift += 1
            }

            result += 1 << (shift - 1)
            divd -= divs << (shift - 1)
        }

        return result * sign
    }

chenbo

编程爱好者

Singapore