Wednesday, October 7, 2015

Divide two integers -- LIKI

class Solution {
public:
    int divide(int dividend, int divisor){      
       unsigned long dvd = dividend < 0 ? -dividend : dividend;
       unsigned long dvs = divisor < 0 ? -divisor : divisor;
       if (dvd < dvs) return 0;
     
       bool nega = (dividend > 0) ^ (divisor > 0);          //nega = true: -xxx; =false: +xxx.
     
       unsigned long originDvs = dvs;
       int power = 0;
       unsigned long result = 0;
     
       while (dvs < dvd){
            dvs = dvs << 1;
            power++;
       }                                    //dvd < dvs now
       while (dvd >= originDvs){
            if (dvd >= dvs){
                 dvd -= dvs;
                 result += (unsigned long) 1 << power;
            }
            while(dvd < dvs){                    //to get biggest dvs < dev everytime
                dvs = dvs >> 1;
                power--;
            }
       }
     
       return nega? -result : result;
   }
};

No comments:

Post a Comment