LeetCode(29)Divide Two Integers

タイトル

Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.

ぶんせき

テーマは*/%の3種類の演算子を使わない条件の下で、2つのintタイプの整数の商を求めることを要求します.
方法1:
明らかに、私たちは求和積算の方法で、商を求めることができますが、この方法のテストはTLEが現れます.ブログを参考にして解決策を提案します:毎回被除数を1倍に増加して、同時にcountも2倍に増加して、もし被除数を超えたら、被除数で現在と更に本操作を継続して、しかし私のテストの結果は依然としてTLEです.だからこの問題の目的は論理演算を考察することである.
方法2:
この方法はブログを参照することに由来するが,この実装は結果オーバーフローの問題を無視し,結果オーバーフロー判定を加える必要がある.

TLE（方法一）コード

// ，   ：Time Limit Exceeded
class Solution {
public:
    int divide(int dividend, int divisor) {

        // 0  0
        if (dividend == 0 || divisor == 0 || abs(divisor) > abs(dividend))
            return 0;

        int sign = ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) ? 1 : -1;

        long long Dividend = abs(dividend), Divisor = abs(divisor);

        long long sum = 0;
        int count = 0, ret = 0;

        while (Divisor <= Dividend)
        {
            count = 1;
            sum = Divisor;
            while ((sum + sum) < Dividend)
            {
                sum += sum;
                count += count;
            }
            Dividend -= sum;
            ret += count;
        }

        if (sign == -1)
            return 0 - ret;
        else
            return ret;
    }
};

ACコード

// ： 
class Solution {
public:
    int divide(int dividend, int divisor) {

        // 0  0
        if (dividend == 0 || divisor == 0)
            return 0;


        // without using * / mod
        // using add
        auto sign = [=](long long x) {
            return x < 0 ? -1 : 1;
        };

        int d1 = sign(dividend);
        int d2 = sign(divisor);

        long long n1 = abs(static_cast<long long>(dividend));
        long long n2 = abs(static_cast<long long>(divisor));

        long long ans = 0;

        while (n1 >= n2) {
            long long base = n2;
            for (int i = 0; n1 >= base; ++i) {
                n1 -= base;
                base <<= 1;
                ans += 1LL << i;
            }
        }
        // int ， , INT_MAX ，int [-2147483648 , 2147483648)
        if (ans > INT_MAX && d1 == d2)
            return INT_MAX;

        int res = static_cast<int>(ans);
        if (d1 != d2) 
            return -res;
        else 
            return res;
    }
};

GitHubテストプログラムソースコード