29. 两数相除(Swift版)

一、题目

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

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

示例 1:

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

示例 2:

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

说明:

1. 被除数和除数均为 32 位有符号整数。
2. 除数不为 0。
3. 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。

二、解题

题目需要考虑溢出，只有当dividend=−2^{31且divisor=-1时才会溢出，所以此时直接返回2}31 − 1即可。
因为除数和被除数都有可能为负数，所以先判断最后的结果是否为负数，然后将除数和被除数都重置为正数。
之后使用while循环，循环减去divisor，并使i累加，最后返回i。
为了提高效率减少循环次数，使用了div进行两倍累加计算i。
时间复杂度为O(m/n) m为dividend,n为divisor。

三、代码实现

    class Solution {
        func divide(_ dividend: Int, _ divisor: Int) -> Int {
            if divisor == -1 && dividend == Int32.min {
                return Int(Int32.max)
            }
            
            let isMinus = (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)
            var dividend = dividend > 0 ? dividend : -dividend
            let divisor = divisor > 0 ? divisor : -divisor

            if (divisor == 1) {
               return isMinus ? -dividend : dividend
            }
            
            var i = 0
            while dividend >= divisor {
                var j = 1
                var div = divisor << 1
                while dividend > div {
                    div <<= 1
                    j <<= 1
                }
                dividend -= div >> 1
                i += j
            }
            return isMinus ? -i : i
        }
    }

Demo地址：github