题目描述

给定两个整数，被除数 dividend 和除数 divisor 。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如truncate(8.345) = 8以及 truncate(-2.7335) = -2

来源，leetcode 每日一题 29. 两数相除

例如：

  1. 输入: dividend = 10, divisor = 3
  2. 输出: 3
  3. 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

又如：

  1. 输入: dividend = 7, divisor = -3
  2. 输出: -2
  3. 解释: 7/-3 = truncate(-2.33333..) = -2

解题思路

  1. 暴力的解法：就是每次用dividend减去一个除数，看需要减多少次，让它变号。这种方法容易时间超限。
  2. 加快暴力解法：上面的复杂度如果是看成O(N)的话，那么很自然想到，他是不是可以被降解成O(logN)呢？从这角度出发，很容易想到每次都是2倍叠加的方式。即第一次是减去divisor，第二次是减去divisor 2, 第三次是减去divisor 2^2，依次类推，当第n次的时候发生符号改变，则说明答案在(29. 两数相除 - 图1)之间，这时只要对29. 两数相除 - 图2继续计算是divisor几倍就可以(即重复上述过程！递归！)

    代码

    1. class Solution {
    2. public:
    3.  int divide(int dividend, int divisor) {
    4.      if(dividend == 0) return 0;
    5.      if(divisor == 1) return dividend;
    6.      if(divisor == -1){
    7.          if(dividend>INT_MIN) return -dividend;// 只要不是最小的那个整数，都是直接返回相反数就好啦
    8.          return INT_MAX;// 是最小的那个，那就返回最大的整数啦
    9.      }
    10.      long a = dividend;
    11.      long b = divisor;
    12.      int sign = 1; 
    13.      if((a>0&&b<0) || (a<0&&b>0)){
    14.          sign = -1;
    15.      }
    16.      a = a>0?a:-a;
    17.      b = b>0?b:-b;
    18.      long res = div(a,b);
    19.      if(sign>0)return res>INT_MAX?INT_MAX:res;
    20.      return -res;
    21.  }
    22.  int div(long a, long b){  // 似乎精髓和难点就在于下面这几句
    23.      if(a<b) return 0;
    24.      long count = 1;
    25.      long tb = b; // 在后面的代码中不更新b
    26.      while((tb+tb)<=a){
    27.          count = count + count; // 最小解翻倍
    28.          tb = tb+tb; // 当前测试的值也翻倍
    29.      }
    30.      return count + div(a-tb,b);
    31.  }
    32. };