算法(力扣001) —— 整数除法

1.力扣题目

 1.给定两个整数 a 和 b ，求它们的除法的商 a/b?

 2.要求：不得使用 乘号 '*'、除号 '/' 、求余 '%' 。

2.结果代码分析

if (a == Integer.MIN_VALUE && b == -1) { return Integer.MAX_VALUE; }

 1.首先，对参数的边界值进行判断。如果被除数a是整形的最小值，并且除数b是-1的情况下，正常运算的结果为被除数a本身。
   实际：结果为整形的最大值，所以需要排除这种情况。遇到情况，直接返回结果即可。
   （1）Integer.MIN_VALUE相关：
   							1.在JDK中，整形类型是有范围的，
   							2.最大值为Integer.MAX_VALUE，即2147483647。
  							3.最小值为Integer.MIN_VALUE，即-2147483648。
  							4.对整形最大值加1，即2147483648。其结果是-2147483648，即Integer.MIN_VALUE。
  							5.对Integer.MIN_VALUE取反或者取绝对值，其结果是-2147483648，即Integer.MIN_VALUE。（因为取反后整形达到超过范围，成为最小值）
   （2）&&相关：
   							1.&&运算符是 短路与 运算。
   							2.如果&&左边的表达式的值是 false，右边的表达式会被直接短路掉，不会进行运算。

int sign = (a > 0) ^ (b > 0) ? -1 : 1;

 2.其次，被除数a和除数b进行正负的判断。如果被除数a和除数b都大于0，则返回-1；如果有一方为负数，则返回1。
   实际：记录a和b是否都大于0后，作用于最终结果的符号判断。
   （1）^（按位异或）相关：
   							1.运算符是 按位异或 运算。
   							2.任意相同二进制位进行^运算，结果为0；任意不同二进制位进行 ^ 运算，结果为1。
   （2）(条件表达式)？表达式1：表达式2 相关：
   							1.先判断条件表达式的值，若为true，运算结果为表达式1；若为false，运算结果为表达式2。

a = Math.abs(a); b = Math.abs(b);

 3.然后，对被除数a、除数b 都取绝对值。 
   （1）Math.abs() 相关：获得其绝对值。如果参数等于 Integer.MIN_VALUE 的值（即能够表示的最小负 int 值），那么结果与该值相同且为负。

int res = 0;

4.再然后，对结果res进行初始化。

for (int i = 31; i >= 0; i--) {
     if ((a >>> i) - b >= 0) {  
         a -= (b << i) ;
         if (res > Integer.MAX_VALUE - (1 << i)) {
               return Integer.MIN_VALUE;
         }
         res += (1 << i);
     }
}

5.再然后，在for循环进行逻辑编写，i从31开始递减，进行循环。（每次尝试从最大的位数开始尝试）
  1）如果 被除数a右移i后，和除数b相减大于0，继续进行判断。
  2）重要逻辑：不能使用除法、乘法后，可以使用减法减去除数b来判断商。
             为了提高代码效率，使用位运算符，让被除数a在减去 除数b的2的i次幂 的情况下去使用减法判断商。
  3）代码优化：res += (1 << i); 这里控制 res 大于等于 INT_MAX
  PS:无符号右移为了将 Int最小值 看成 2147483648，同时不用担心越界。以(a >>> i) - b >= 0的格式，可以防止出现：除数b为最小值，导致永远为true的情况。
  
  （1）>>>相关：在表达式中执行无符号右移。

return sign == 1 ? res : -res;

6.最后，因为不能使用乘号，所以将乘号换成三目运算符

3.完整的结果代码

// 时间复杂度：O(1)
        public int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == -1)
        return Integer.MAX_VALUE;
        int sign = (a > 0) ^ (b > 0) ? -1 : 1;
        a = Math.abs(a);
        b = Math.abs(b);
        int res = 0;
        for (int i = 31; i >= 0; i--) {
        // 首先，右移的话，再怎么着也不会越界
        // 其次，无符号右移的目的是：将 -2147483648 看成 2147483648

        // 注意，这里不能是 (a >>> i) >= b 而应该是 (a >>> i) - b >= 0
        // 这个也是为了避免 b = -2147483648，如果 b = -2147483648
        // 那么 (a >>> i) >= b 永远为 true，但是 (a >>> i) - b >= 0 为 false
        if ((a >>> i) - b >= 0) { // a >= (b << i)
        a -= (b << i);
        // 代码优化：这里控制 res 大于等于 INT_MAX
        if (res > Integer.MAX_VALUE - (1 << i)) {
        return Integer.MIN_VALUE;
        }
        res += (1 << i);
        }
        }
        // bug 修复：因为不能使用乘号，所以将乘号换成三目运算符
        return sign == 1 ? res : -res;
        }

4.代码出处和教学出处

     代码和逻辑相关原文链接：
    	作者：tangweiqun
     	来源：力扣（LeetCode）
     	原文链接：https://leetcode-cn.com/problems/xoh6Oh/solution/jian-dan-yi-dong-javac-pythonjs-zheng-sh-e8r6/
	
	Integer.MIN_VALUE相关原文链接：
		来源：CSDN
		原文链接：https://blog.csdn.net/wujumei1962/article/details/44104895
		
	and（&）运算 （按位与）^（按位异或）相关原文链接：
	    来源：CSDN
		原文链接：https://blog.csdn.net/zhongjling/article/details/8004103

5.博主 边学习边记录算法的学习

欢迎各位大佬评论、指点，第一次写博客有很多失误，希望可以帮助小部分人。
祝大家早日推开算法成神之路。