LeetCode 29 Divide Two Integers（兩個整數相除）（*）

LeetCode 29 Divide Two Integers（兩個整數相除）（*）

翻譯

不用乘法、除法、取余操作，將兩個數相除。

如果它溢出了，返回MAX_INT

原文

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

If it is overflow, return MAX_INT.

代碼

一心撲到了遞歸上，可惜沒能寫出來…………煩躁至極還是找了別人的答案……

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(!divisor) return INT_MAX;
        if(divisor == 1) return dividend;
        if(divisor == -1) {
            if(dividend == INT_MIN) return INT_MAX;
            else return -dividend;
        }

        bool s1 = dividend < 0;
        bool s2 = divisor < 0;

        unsigned int nom = s1 ? -dividend : dividend;
        unsigned int den = s2 ? -divisor : divisor;

        unsigned int rem = 0;
        unsigned int quot = 0;

        for(int i = 31; i >= 0; --i) {
            rem <<= 1;
            rem |= (nom >> i) & 1;
            if(rem >= den) {
                rem -= den;
                quot |= (1 << i);
            }
        }

        return s1^s2? -quot : quot;
    }
};

再來兩個代碼……（慚愧……）

public class Solution
{
    public int Divide(int dividend, int divisor)
    {
        //1. check overflow: 2 ways of over flow 1) 0 divisor; 2) int.Minvalue/(-1)
        if (divisor == 0 || dividend == int.MinValue && divisor == -1) return int.MaxValue;
        //2. calculate sign
        int sign = dividend > 0 ^ divisor > 0 ? -1 : 1, result = 0;
        long m = Math.Abs((long)dividend), n = Math.Abs((long)divisor);
        //3. looping from 1 to possible maximum pow(2, x) to add into result
        while (m >= n)
        {
            long subN = n;
            for (int subCount = 1; m >= subN; subCount <<= 1, subN <<= 1)
            {
                m -= subN;
                result += subCount;
            }
        }
        return result * sign;
    }
}

public class Solution
{
    public int Divide(int dividend, int divisor)
    {
        if (divisor == 1) return dividend;
        if (dividend == int.MinValue && divisor == -1 || divisor == 0) return int.MaxValue;
        int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1, result = 0;
        long dvd = Math.Abs((long)dividend), dvs = Math.Abs((long)divisor);
        while (dvd >= dvs)
        {
            long sub = dvs;
            int subR = 1;
            while (dvd >= (sub << 1))
            { sub <<= 1; subR <<= 1; }
            dvd -= sub;
            result += subR;
        }
        return sign * result;
    }
}