題目：
29、兩數相除
給定兩個整數，被除數 dividend 和除數 divisor，將兩數相除，要求不使用乘法、除法和 mod 運算子，
回傳被除數 dividend 除以除數 divisor 得到的商，
整數除法的結果應當截去（truncate）其小數部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:
輸入: dividend = 10, divisor = 3
輸出: 3
解釋: 10/3 = truncate(3.33333…) = truncate(3) = 3
示例 2:
輸入: dividend = 7, divisor = -3
輸出: -2
解釋: 7/-3 = truncate(-2.33333…) = -2
提示：
被除數和除數均為 32 位有符號整數，
除數不為 0，
假設我們的環境只能存盤 32 位有符號整數，其數值范圍是 [?231, 231 ? 1]，本題中，如果除法結果溢位，則回傳 231 ? 1，
題解思路：
最簡單的想法就是把兩個數都變成正的，然后被除數不斷的減去除數直到小于除數為止，最后再加上正負號，可以用異或判斷兩個數的正負性是否相同，而溢位的唯一可能是結果等于 2^31，當然，這種方法會在用例(-2147483648, -1) 超時，，，
不超時思路：
顯然超時是因為兩個數的逼近太慢，因為不能用除法，只改變被除數就必須用減法，太慢了，
所以考慮改變除數，可以不斷的自加，相當于乘 2，就可以快速的逼近被除數了.
比如 (100, 2)，2 不斷自加最多到 64 還小于 100，那么 100 就應該先減去 64 以最快逼近，而減去 64 就相當于減去 32 個 2，
但因為不能用除法，32 不是顯然得到的，所以還需要一個變數初始為 1，隨著除數自加而自加，以表示等價的除數個數，
100 減去 64 后，被除數和除數變為 (36, 2)，然后回圈這個程序即可，
進一步的，后面明顯有很多重復計算，所以可以把程序中的值 4、8、16、32、64 及等價的除數個數保存下來，再倒序遍歷即可，
題解python代碼：
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
m, n, flag = abs(dividend), abs(divisor), int(dividend^divisor >=0)
d, w = [], 1
while n <= m:
d.append((n, w))
n += n
w += w
res = 0
for n, w in d[::-1]:
if m >= n:
m -= n
res += w
return min([-res, res][flag], 2147483647)
作者：huozhixue
鏈接：https://leetcode-cn.com/problems/divide-two-integers/solution/python3-jian-ji-by-huozhixue-xgo6/
來源：力扣（LeetCode）https://leetcode-cn.com/problems/divide-two-integers/
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/259478.html
標籤：python