leetcode-29 Divide Two Integers

題意: 實現除法,但不能使用乘法,除法或mod

解題思路: 這題應該是為了模擬某些平台,不能使用上述指令的情況,所以利用bit manipulation來實現二進位除法, 演算法如下=>
x/y, 把y做left shift,到超過x為止,將左移的量減一,而後加到答案裡,再把x減去y左移減一的量,以此類推

ps. 須注意 加減號比左右移符號更優先,故該使用括號的時候就要用XD
可參考: MSDN

C++  code:

class Solution {
public:
    int divide(int dividend, int divisor) {
        long long ans=0;
        long long ok=1;
        long long m=(long long)dividend;
        long long n=(long long)divisor;
        if(m<0)
        {
            ok=~ok+1;
            m=~m+1;
        }
        if(n<0)
        {
            ok=~ok+1;
            n=~n+1;
        }
        
        while(m>=n)
        {
            long long t=0;
            long long c=n;
            
            while(m>=c)
            {
                t++;
                c=c<<1;
            }
            t--;
            ans=ans+((long long)1<<t);
            m=m-(n<<t);
        }
        
        if(ok==-1)
            ans=~ans+1;
        if(ans>INT_MAX||ans<INT_MIN)
            return INT_MAX;
        else
            return ans;
    }
};