Divide Two Integers

描述

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

分析

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

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

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

代码

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

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