LeetCode OJ: 29. Divide Two Integers 兩數相除

題目連結 https://leetcode.com/problems/divide-two-integers/，題目要求不可以用乘法、除法與餘數運算子。從題目分類的Tag上，筆者看到了Binary Search後，就想到位元運算子，只是筆者考慮欠周詳，因為送出後一直得到Wrong Answer阿，原來是忘了考慮Overflow的問題，於是看了此Discuss後，寫了如下的程式碼：

class Solution {
public:
    int divide(int dividend, int divisor) {
        if ( divisor == 0 )
            return INT_MAX;

        // Handling overflow
        if( dividend == INT_MIN ) {
            if( divisor == -1) return INT_MAX;
            else if( divisor == 1)  return INT_MIN;
            else return ( (divisor & 1 ) == 1 ) ? divide( dividend + 1, divisor) : divide( dividend >> 1, divisor >> 1 );
        }

        if( divisor == INT_MIN ) return 0;

        int sign = (dividend >= 0) ^ (divisor >= 0) ? -1: 1;
        long dEnd = abs(dividend);
        long dSor = abs(divisor);

        int quotient = 0;

        while(dEnd >= dSor) {
            long tmpSor = dSor, q = 1;

            while( dEnd >= (tmpSor << 1) ) {
                tmpSor = tmpSor << 1;
                q = q << 1;
            }

            dEnd -= tmpSor;
            quotient += q;
        }

        return sign == 1 ? quotient: -quotient;
    }
};

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。