sourcecode

Tuesday, November 27, 2012

Divide Two Integers

http://www.leetcode.com/onlinejudge
Divide two integers without using multiplication, division and mod operator.

class Solution {
public:
    int divide(int dividend, int divisor) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int y = dividend;
        int x = divisor;
        bool signFlag = 0;
        if (y > 0){
            y = -y;//defualt for
            dividend = y;
            signFlag = 1;
        }
        if (x > 0){
            x = -x;//both negatives
            divisor = x;
            signFlag = !signFlag;
        }
        //     10|11
        //     00|01
        int totalShift = 0;
        while(y < x){
            ++totalShift;
            y >>= 1;
        }
        if (y == x) ++totalShift;
        --totalShift;
        // |divisor<<totalShift|    <=   |dividend|
        int result = 0;
        for(y = dividend, x = divisor<<totalShift;//y <= x
                totalShift >= 0;
                --totalShift){
            result <<= 1;
            if (y <= x){
                ++result;
                y -= x;
            }
            x >>= 1;
        }
        if (signFlag){
            result = - result;
        }
        return result;
    }
};

No comments: