来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/divide-two-integers
题目描述
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1: 输入: dividend = 10, divisor = 3 输出: 3 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3 示例 2: 输入: dividend = 7, divisor = -3 输出: -2 解释: 7/-3 = truncate(-2.33333..) = -2 提示： 被除数和除数均为 32 位有符号整数。 除数不为 0。 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
解题思路
很有价值的一道题，由于限制了不能使用long 和除法，需要考虑各种边界问题和使用减法或者位运算来代替。
首先判断边界，已知除数不为0：
在被除数等于-231时，如果除数是1，则返回-231，如果除数是-1则返回溢出，也就是231-1。
如果除数是-231判断被除数是否为-231如果是，则返回1，如果不是则返回0。
被除数是0时，返回0。
然后解决符号的问题，如果两数同号为正异号为负，并且int中负数域比正数大，可以避免溢出，所以全部转换为负数，最后再根据原始符号的结果重新赋符号。
最暴力的想法是将被除数不断的减去除数并且计数，计数就是商，不出所料的超时了。
采用快速加法的思想，建立一个除数集，下标为n就表示除数左移n个位置，也就是除数 * 2n-1这个数，要注意除数集的元素也可能在计算过程溢出，要进行判断，然后逆序将其被被除数减去，如果减去结果小于等于0，则表示这个数也是商的一部分，加入计数。
代码展示
class Solution { public: int divide(int dividend, int divisor) { int iRet = 0; bool bMinus = false; if(dividend == INT_MIN) { if(divisor == 1) return INT_MIN; if(divisor == -1) return INT_MAX; } if(divisor == INT_MIN) { if(dividend == INT_MIN) return 1; else return 0; } if(dividend == 0) return 0; if(dividend > 0) { bMinus = !bMinus; dividend = -dividend; } if(divisor > 0) { bMinus = !bMinus; divisor = -divisor; } vector<int> divisors = {divisor}; while(dividend - divisors.back() <= divisors.back()) { divisors.push_back(divisors.back() + divisors.back()); } for(int i = divisors.size() - 1; i >= 0; i--) { if(dividend - divisors[i] <= 0) { dividend -= divisors[i]; iRet += 1 << i; } } return bMinus? -iRet: iRet; } };
运行结果
