Use only int and no fancy bit manipulation C++ solution


  • 0
    S

    The basic idea is to use subtraction. To speed up, every time the subtraction is successful, make the divisor two times bigger. If the subtraction is not successful and the divisor is bigger than original divisor value, make the divisor half size. To deal with overflow, use negative range of "int" to do the process mention above.

    class Solution {
    public:
        int divide(int dividend, int divisor) {
            if(divisor==0 || dividend==0) return 0;
    
            //get sign
            int sign;
            if(dividend>0 && divisor>0 || dividend<0 && divisor<0)
                sign=1;
            else
                sign=-1;
    
            // to negative
            dividend = dividend<0 ? dividend : 0 - dividend;
            divisor =  divisor <0 ? divisor : 0 - divisor;
    
            int res=0;
            int tryDiv=divisor;
            int times=1;
            while(dividend < 0 || (dividend>0 && tryDiv != divisor)){
                if(dividend > 0) {
                    dividend += tryDiv;
                    res += times;
                    tryDiv = tryDiv>>1;
                    times = times>>1;
                    continue;
                }
    
                dividend -= tryDiv;
                res -= times;
                if(dividend < tryDiv) {
                    tryDiv += tryDiv;
                    times += times;
                }
            }
            if(dividend > 0) res++;
    
            if(sign>0 && res==INT_MIN) return INT_MAX;
            return sign<0 ? res : 0-res;
        }
    };
    
    

  • 0
    S

    A better version:

    class Solution {
    public:
        int divide(int dividend, int divisor) {
            if(divisor==0 || dividend==0) return 0;
            //get sign
            int sign = dividend<0 ^ divisor<0 ? -1 : 1;
            // to negative
            dividend = dividend<0 ? dividend : -dividend;
            divisor =  divisor <0 ? divisor : -divisor;
    
            int res=0;
    
            int minDiv = INT_MIN>>1;
            while(dividend<=divisor){
                int tryDiv=divisor;
                int times=1;
                while(tryDiv >= minDiv && dividend <= tryDiv<<1 ){
                    tryDiv <<=1;
                    times <<=1;
                }
                dividend -= tryDiv;
                res -= times;
            }
    
            if(sign>0 && res==INT_MIN) return INT_MAX;
            return sign<0 ? res : 0-res;
        }
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.