leetcode 29. Divide Two Integers

Given two integers 

dividend

 and 

divisor

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

Return the quotient after dividing 

dividend

 by 

divisor

.

The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3      

Example 2:

Input: dividend = 7, divisor = -3
Output: -2      

Note:

• Both dividend and divisor will be 32-bit signed integers.
• The divisor will never be 0.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

轉載自：https://blog.csdn.net/lixq05/article/details/81157304

這個思路比較清晰

class Solution {
public:
long long ABS(long long a)
{
    return a > 0 ? a : -a;
}
int divide(int dividend, int divisor)
{
    if (divisor == 0 || (dividend == INT_MIN && divisor == -1))
        return INT_MAX;
    long long a = ABS((long long)dividend);
    long long b = ABS((long long)divisor);
    long long sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
    long long res=0;
    long long tmp[33], times[33];
    //第一組資料填充
    tmp[0] = b;
    times[0] = 1;
    int index = 0;
    //一直填充到臨界大于a的位置
    while (a >= tmp[index] && index < 33)
    {
        index++;
        tmp[index] = tmp[index - 1] + tmp[index - 1];
        times[index] = times[index - 1] + times[index - 1];
    }
    //周遊填充資料
    for (int j = index - 1; j >= 0; j--)
    {
        while (a >= tmp[j])
        {
            res += times[j];
            a -= tmp[j];
        }       
    }
    res = (sign == 1) ? res : -res;
    return (int)res;
}
};