题目

给定两个整数，被除数 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。

思路

乘除取余都不让用，那就位运算走起
那问题是，如何设计位运算？
商 * 除数 + 余数 = 被除数，这个式子大家肯定都清楚
在本题中，余数是可以忽略的，当然，余数肯定是小于除数的
那么我们就可以理解为
商就是被除数减去N多个除数，直到被除数 - N个除数变得小于除数
最终，N就是这个商了

剩下的，就是实现了

代码

Python3

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == 0:
            return 0

        # 并非取巧，题中只存在32位有符号数字
        if dividend == -(2^31) & divisor == -1 :
            return 2^31 - 1

        import math
        up = int(math.fabs(dividend))
        down = int(math.fabs(divisor))
        result = 0
        while up >= down:
            base = down
            count = 1

            while up >= (base << 1):
                base <<= 1
                count <<= 1

            result += count
            up -= base

        if dividend ^ divisor < 0:
            result = -result

        # 并不符合32位有符号数字的题干
        # if result < -(1 << 31) or result > ((1 << 31) - 1):
        #     result = (1 << 31) - 1

        return result


int1 = -2147483648
int2 = -1
solution = Solution()
print(solution.divide(int1, int2))

Golang

func divide(dividend int, divisor int) int {
    if dividend == -(1 << 31) {
        if divisor == -1 {
            return 1 << 31 - 1
        }
        if divisor == 1 {
            return -(1 << 31)
        }
    }
    positive := false
    if dividend > 0 && divisor > 0 || dividend < 0 && divisor < 0 {
        positive = true
    }
    
    if dividend > 0 {dividend = -dividend}
    if divisor > 0 {divisor = -divisor}
    
    _, ans := dfs(dividend, divisor, 1)
    
    if positive {
        return ans
    } else {
        return -ans
    }
}

func dfs(dividend, divisor int, count int) (int, int){
    if dividend > divisor {
        return dividend, 0
    }
    
    d, c := dfs(dividend, divisor + divisor, count + count)
    if d <= divisor {
        return d - divisor, count + c
    }
    
    return d, c
}

以上，共勉

---

欢迎大家关注我的公众号

半亩房顶