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.

题目大意 不适用乘、除、mod的情况下，计算两数的商，注意溢出的情况。

，所以使用位运算去求i比较方便

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend==0){
            return 0;
        }
        if(dividend==INT_MIN&&divisor==-1){
            return INT_MAX;
        }
        if(dividend==INT_MAX&&divisor==1){
            return INT_MAX;
        }
        if(dividend==INT_MIN&&divisor==1){
            return INT_MIN;
        }
        if(dividend==INT_MAX&&divisor==-1){
            return INT_MIN;
        }
        //使用位运算，不管dividend和divisor怎么变化，2的i次方求和与divisor的积一定会等于dividend，
        int flag =1;
        if(dividend<0){
            flag*= -1;
        }
        if(divisor<0){
            flag*= -1;
        }
        long long ans =0;
       
        long long m = abs((long long)dividend);
        long long n = abs((long long)divisor);
        while(m>=n){
            long long i=1;
            long long a=n;
            while((a<<1)<m){
                a=a<<1;
                i=i<<1;
            }
            ans+=i;
            m-=a;
        }
        //cout<<ans<<endl;
        return flag*ans;
    }
};