- 题目：
- 分析：
- 方向：
- 额外：
- 优化：【脱离细节看整体，越看越混：脱离整体看细节，越看越杂】
- 代码：
- 第一版：
- 第二版：
- 第三版：
- 总结：
给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。
注意：
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31−1]。本题中，如果除法结果溢出，则返回 2^31 − 1提示:
-2^31 <= a, b <= 2^31 - 1
b != 0
示例 1：
输入：a = 15, b = 2 输出：7 解释：15/2 = truncate(7.5) = 7
示例 2：
输入：a = 7, b = -3 输出：-2 解释：7/-3 = truncate(-2.33333..) = -2
示例 3：
输入：a = 0, b = 1 输出：0
示例 4：
输入：a = 1, b = 1 输出：1分析：
题目中给定如下需求：
- 不得使用 * / % 等计算符号
- 结果取整数部分，且包含一般的正负符号
- 当结果溢出，返回MAX_VALUE
无法使用乘除等计算方式，可以想到乘除的本质在计算器内部就是加法(减法)实现的。故这里可以采取循环x=被除数-除数。【这里需要特殊注意，做减法的时候，需要被减数和减数处于同一正负性】后继续执行该逻辑，直到被除数不大于除数
额外：- 必然越界问题：当传入一些特定值时，结果必然溢出，此处可以直接在函数开始位置定义逻辑。如当a=-2^31,b=1,理想结果是2^31，但是在int中已经溢出。
- 非必然越界问题：在计算过程中或者逻辑执行中出现越界问题，此处需要特殊处理。如当处理减数和被减数为同一正负性的时候，如果存在数字为-2^31，那么转化为正数就会越界，而对应的最大正数转化为负数却不会越界，所这里可以将所给数字都化为负数来避免非必然越界问题。
- 虽然将优化写在了这个位置，但是本人还是不建议在开始阶段【第一版代码未通过】就着想优化逻辑。
- 使用减法方式需要被减数和减数循环进行相减，如果两者差距很大，可能需要执行n次。所以优化方向就在于减少相减次数，提高代码效率。
描述：只实现减法过程，不关心执行次数【先实现功能，再优化细节】
class Solution {
public int divide(int a, int b) {
int max = Integer.MAX_VALUE; //2^31-1 2147483647
int min = Integer.MIN_VALUE; //-2^31 -2147483648
//01、处理必然溢出 (a=min & b=-1)
if(a==min && b==-1) return max;
//02、记录符合，除法结果需要含正负性，正负性即是传入a，b自带的属性
//异或计算：同为false，不同为true。 如果a，b正负性不同那么flag=false
boolean flag = (a>0)^(b>0)?false:true;
//03、a，b 相减前正负性需保持一致
//04、防止a，b中取值为min，转为正数溢出，故全部转移为负数
//05、定义循环次数 count 作为返回结果
a = a>0?-a:a;
b = b>0?-b:b;
int count = 0;
//06、a，b都已是负数，负数的减法如下：a-b实则是 负数的a 加 正数的b得到新的结果。所以循环过程中需要a大于b
//在负数之中，一个值越大，那么绝对值越小。实现除法底层是是绝对值的计算 ，所以只有绝对值a大于b，那么才有计算的意义，否则停止循环
while(a<=b){
a-=b;
count++;
}
//07、返回结果，但是需要结合flag，返回对应正负性结果
return flag?count:-count;
}
}
第二版：
此版是二十一画通过阅读@老汤 该大佬的解题思路得出的改良版，大致上是按照该大佬的思路进行解题。第一版解法是被减数(a)每次循环中减一个减数(b)，这种方式执行次数可以得出，process_Count<=a/b+1，此处可以降低执行次数，每次循环中可以减两个减数(b)，虽然第二版提高效率并不高效，但是也提供了一种思路。
class Solution {
public int divide(int a, int b) {
int max = Integer.MAX_VALUE; //2^31-1 2147483647
int min = Integer.MIN_VALUE; //-2^31 -2147483648
//01、处理必然溢出 (a=min & b=-1)
if(a==min && b==-1) return max;
//02、记录符合，除法结果需要含正负性，正负性即是传入a，b自带的属性
//异或计算：同为false，不同为true。 如果a，b正负性不同那么flag=false
boolean flag = (a>0)^(b>0)?false:true;
//03、a，b 相减前正负性需保持一致
//04、防止a，b中取值为min，转为正数溢出，故全部转移为负数
//05、定义循环次数 count 作为返回结果
a = a>0?-a:a;
b = b>0?-b:b;
int count = 0;
//06、第一版解法是被减数(a)每次循环中减一个减数(b),这种方式执行次数可以得出，process_Count<=a/b+1
// 此处可以降低执行次数，每次循环中可以减两个减数(b)，虽然第二版提高效率并不高效，但是也提供了一种思路
while(a<=b){
//07、如果|a|>=2|b|，那么可以一次性减两个减数(b) ，此处b+b可能溢出，所以需要加入判断逻辑(其实这里有点是取巧，直接使用进制位来判断溢出)
// 0xc0000000 是 -2^31的一半，这里如果不喜欢用进制，可以换成【if( b>=min-b && a<=(b+b))】
// 需要写成b>=min-b ，如果写成b+b=0xc0000000 && a<=(b+b)){
a-=(b+b);
count+=2;
}else{
// 第一版逻辑
a-=b;
count+=1;
}
}
//08、返回结果，但是需要结合flag，返回对应正负性结果
return flag?count:-count;
}
}
第三版：
此版同样是从@老汤 大佬题解中得出的思路，一版和二版的执行次数都是由被减数和减数之前的差距来决定，所以时间复杂度不稳定，也存在变数。此版本是解决时间复杂度的解法，此处设x，y：x是被减数，y是减数，第一版和第二版的底层思想就是从x中一个一个减去y，或者是减去两个y。
那么第三版的实现，是按照 2^i 从x中减去2^i个y 【已知int类型，0<=i<=31】
所以需要遍历32次即可实现整数相除。具体逻辑空说不太清晰，我会将逻辑拆分揉碎体现在实现代码中。
class Solution {
public int divide(int a, int b) {
int max = Integer.MAX_VALUE; //2^31-1 2147483647
int min = Integer.MIN_VALUE; //-2^31 -2147483648
//01、处理必然溢出 (a=min & b=-1)
if(a==min && b==-1) return max;
//02、记录符合，除法结果需要含正负性，正负性即是传入a，b自带的属性
//异或计算：同为false，不同为true。 如果a，b正负性不同那么flag=false
boolean flag = (a>0)^(b>0)?false:true;
//03、a，b 相减前正负性需保持一致
//04、新的版本将符号保持为整数，下面会体现为何要保存为正数
//05、定义count变量 作为结果存储
//06、执行abs函数后，会有几个特殊情况。 当a或者b = min的时候，abs出来的结果也是min，数组是个圈 ，溢出之后系统返回的值还是自身
// min = abs(min) max = abs(max) 樂
//07、想着重处理下当b=min的情况，如果b=min&&a<>min，恒等式|a|<|b|那么结果必然是0
// 如果b==min&&a==b 那么结果必然是1，在这里将特殊逻辑处理，下面循环逻辑就更容易理解
// 这样就处理了 b为负数的情况
if(b==min && a!=min) return 0;
if(b==min && a==b) return 1;
a = Math.abs(a); // a正负性 不确定
b = Math.abs(b); // b>=0 恒成立
int count = 0;
//05、循环逻辑
for(int i=31;i>=0;i--){
// 这里循环32次，因为默认存储是2进制的，a的显示可能是 【10100100 10101010 10010100 10110100】 i代表二进制的位数
// 其实这里循环就是在找因数，已知积=a,已知一个因数为b，那么求另外一个因数（这里暂且认为因数，因为可能不是整除的，所以先把商指代为因数）。我们无法使用除法，所以无法直接得出因数，只能通过从a本身的最大因数开始寻找正确的因数。
// 因数： 2^31 2^30 2^29 2^28 ... 2^2 2^1 2^0
// 举例： x * b <= a ，（x∈【2^31 2^30 2^29 2^28 ... 2^2 2^1 2^0】）
// 当 x 太大了，我们就缩小x，直到 符合条件，后将 a=a-xb,继续循环
// 因为 a-xb之后，在该二进制i位不可能继续为1，因为 x在二进制中代表第i位=1，减去之后该位肯定变成0了。所以可以继续循环下一位，也就是i--
if((a>>>i)-b>=0){
//这里(a>>>i)-b>=0 不可以写成 (a>>>i)>= b，如果按照后者写法，当a此次循环为min的时候，会导致min绝对值虽然大于b，但是因为min>=b不成立而产生错误逻辑
// 正确写法应该是将判断式放在左边，如果a=min,那么a-b 会溢出，溢出成一个正数，此时符合逻辑，a的绝对值确实比b的大，所以应该走循环内的代码。 写左边没有任何影响，如果a>>i 一定是大于0的正数，同时b也大于0，所以a和b的运算是可以的。
// ①都为正数 ②符合减数逻辑
a-=(b<
总结：
个人觉得第一版和第二版比较简单，第三版位运算确实比较复杂。二十一画应该也只能想到前两种，第三种觉得可以作为了解一下。知道有这么个解法就可以。
另外其实，这道题的关键是在于，减法需要保持符号一致，如果都为正数，那么min有越界的可能，需要单独处理，如果都为负数，那么正数转负数不存在越界的情况，如此书写逻辑便简单多了。
大家好，我是二十一画，感谢您的品读，如有帮助，不胜荣幸~
