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:
Post a Comment