029 Divide Two Integers[M]

02-25

1 題目描述

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

難度：Medium

2 題目樣例

無。

3 題意分析

要求不用乘法，除法和取模運算，算出兩個數字的商。

4 思路分析

我在思考了足足五秒鐘，腦子裡排除了各種"這...這也能算？"之後，想到了本學期在CSAPP中學到的內容。

既然不允許使用乘除和取模，那我們就從機器碼最底層的運算入手，直接使用位運算對除法進行模擬就可以了。

出於取（偷）巧（懶）的考慮，我們可以把變數都設置成64位的，這樣就保證了中間變數不溢出，最後的結果特殊判斷即可。

注意其中一步，在取絕對值的時候，要使用強制類型轉換。否則可能會造成數據溢出。

代碼實現如下：

class Solution { public: int divide(int dividend, int divisor) { int sign=1; if(dividend*divisor<0) sign=-1; long long ans=0; long long m=abs((long long)dividend); long long n=abs((long long)divisor); while(m>=n) { long long temp=n; long long plus=1; while((temp<<1)<m) { temp<<=1; plus<<=1; } m-=temp; ans+=plus; } if(sign<0) ans=-ans; if(ans>INT_MAX) return INT_MAX; else return ans; }};

5 後記

學以致用？

CSAPP和演算法導論里的內容似乎也是面試考察的重點內容呢......我已經不知道第多少次看到相關的題目了。