【算法day22】两数相除——给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。

29. 两数相除

给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

返回被除数 dividend 除以除数 divisor 得到的 商 。

注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−231, 231 − 1] 。本题中，如果商 严格大于 231 − 1 ，则返回 231 − 1 ；如果商 严格小于 -231 ，则返回 -231 。

https://leetcode.cn/problems/divide-two-integers/description/

方法二、根据递归法总结进行化简

首先根据方法一里面的描述，我们已经理解 并得出了这个递归的过程，所以我们来进一步优化迭代的运算，

为了节省函数调用次数，用循环来代替递归的过程即可
我们先找到最大的那个可以减去的数字，
然后再进行右移找尽可能大的那个可以减去的数字

有一个细节是要把整数变成负数后再进行运算，因为补码的表示范围中，负数比正数多出来一位，
因此用减法运算可以减少边界判断的次数。

我在代码里使用了移位，

maxSub <<= 1; // 被除数翻倍
// 也可以写成 maxSub+=maxSub;

上下两种写法效果和结果完全一样，
移位据说更省，

但是我想现代的编译器，应该会自己优化这样的运算。

if (ratio == 0) {ratio = 1;
}

这里的判断不可以省略，
因为32/2 = (32-16-8-4-2-2)/2 +8+4+2+1+1= 8+4+2+1+1 = 16
否则会输出15，答案错误

class Solution {
public:int divide(int dividend, int divisor) {// 处理边界情况if (dividend == INT_MIN && divisor == 1)return INT_MIN;if (dividend == INT_MIN && divisor == -1)return INT_MAX;if (divisor == 0)  // 除0是非法的return 0;// 两个正数，得到signal true，一正一负，都得到signal// false，两个负数得到signal true；bool signal = true;if (dividend > 0) {dividend = -dividend;signal = !signal;}if (divisor > 0) {divisor = -divisor;signal = !signal;}int maxSub = divisor;int ans = 0, ratio = 1;// 注意下面的计算都是负数！while (maxSub > dividend - maxSub) {maxSub <<= 1; // 被除数翻倍// 也可以写成 maxSub+=maxSub;ratio <<= 1;  // 倍率翻倍}// 先移动到最左边找到了最大的ratiowhile (dividend <= divisor) {// 逐步右移回去if (dividend - maxSub >= maxSub && dividend - maxSub <= 0) {ans += ratio; // 如果找到了当前合适的最大的maxSub就扣除并添加倍率dividend -= maxSub;}maxSub = maxSub >> 1;ratio = ratio >> 1;if (ratio == 0) {ratio = 1;}}if (!signal) {return -ans;}return ans;}
};

方法一、递归法：

例如10/3 = （10-6-3）/3+2+1 这个等式成立

所以我们应该先去找一个最小的X，使得X*2大于等于10，可以知道X=3，6，12，24，48……这样翻倍，
由于当X = 6的时候12大于10，此时可以进行运算10-6 = 4，

运算后剩下4，再对4重复上面的过程，4-X<3可知X=3，

因此可以每次都X+=X，并且假设ans=1跟着X每次都ans+=1，

• X=3 ，ans=1
• X=6，ans=2；
• X=12, ans=4；
• X=24,ans =8 （3*8=24） 这说明这个ans就是我们要求和的值。

因此可以找到10/3的时候，ans = 2+1+0 = 3，也就是我们的10/3的答案。

class Solution {
public:int divide(int dividend, int divisor) {if (divisor == 0) {return 0;}//处理特殊情况，边界情况if (dividend == INT_MIN && divisor == 1) {return INT_MIN;}if (dividend == INT_MIN && divisor == -1) {return INT_MAX;}// 全都变成负数，然后再做加减法if (dividend > 0)return -divide(-dividend, divisor);if (divisor > 0)return -divide(dividend, -divisor);if (dividend > divisor) {return 0;}int maxSub = divisor;int ans = 1; // 每次都加上这个最大的倍数while (dividend - maxSub <= maxSub) {maxSub += maxSub;ans += ans;}return ans + divide(dividend - maxSub, divisor);}
};