题目描述

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

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

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
示例 2:

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

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

思路解析

非常简单的思路就是除数-被除数的次数，有多少就是多少
但是会出现一个问题，就是被除数很小，除数很大，时间复杂过高，利用位运算加速。
被除数每次翻倍，结果也翻倍
当不能翻倍的时候，回归开始，重复计算

class Solution:

    def divide(self, a, b):
        '''
        正负号
        越界
        =0
        :param a:
        :param b:
        :return:
        '''
        sign = 1 if a ^ b >= 0 else -1
        a = abs(a)
        b = abs(b)
        if b == 0 or a < b:
            return 0
        res = 0
        while a >= b:
            temp, add = b, 1
            while a >= temp:
                a -= temp
                res += add
                add <<= 1
                temp <<= 1
        res *= sign

        if res > 2 ** 31 - 1:
            return 2 ** 31 - 1
        if res < -2 ** 31:
            return -2 ** 31
        return res

AC29