Divide Two Integers

描述

Divide two integers without using multiplication, division and mod operator.

分析

不能用乘、除和取模，那剩下的，还有加、减和位运算。

最简单的方法，是不断减去被除数。在这个基础上，可以做一点优化，每次把被除数翻倍，从而加速。

注意，写代码的时候，禁止使用 long.

代码

  1. // Divide Two Integers
  2. // 时间复杂度O(logn)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     int divide(int dividend, int divisor) {
  6.         if (dividend == 0) return 0;
  7.         if (divisor == 0) return INT_MAX;
  9.         // 当 dividend = INT_MIN，divisor = -1时，结果会溢出
  10.         if (dividend == INT_MIN) {
  11.             if (divisor == -1) return INT_MAX;
  12.             else if (divisor < 0)
  13.                 return 1 + divide(dividend - divisor, divisor);
  14.             else
  15.                 return - 1 + divide((dividend + divisor), divisor);
  16.         }
  17.         if(divisor == INT_MIN){
  18.             return dividend == divisor ? 1 : 0;
  19.         }
  21.         int a = dividend > 0 ? dividend : -dividend;
  22.         int b = divisor > 0 ? divisor : -divisor;
  24.         int result = 0;
  25.         while (a >= b) {
  26.             int c = b;
  27.             for (int i = 0; a >= c;) {
  28.                 a -= c;
  29.                 result += 1 << i;
  30.                 if (c < INT_MAX / 2) { // prevent overflow
  31.                     ++i;
  32.                     c <<= 1;
  33.                 }
  34.             }
  35.         }
  37.         return ((dividend^divisor) >> 31) ? (-result) : (result);
  38.     }
  39. };

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/simulation/divide-two-integers.html