一、题目
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
说明:
- 被除数和除数均为 32 位有符号整数。
- 除数不为 0。
- 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。
二、解题
题目需要考虑溢出，只有当dividend=−231且divisor=-1时才会溢出，所以此时直接返回231 − 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
