力扣LeetCode第29题：两数相除，beat100%解法

思路
   官方题解中有快速乘，那当然也就有快速除。思路就是模拟手动盘算除法，二进制的除法和十进制也非常类似  解题过程
   （1）起主要把除数和被除数“对齐” （2）然后除数和被除数举行比力，假如小于被除数则这一位商0，否则商1 （3）把每一位的01组装起来就是最终的结果 里面的一些边界题目还必要注意处理惩罚一下。  复杂度
时间复杂度: O(logN)，其中N为被除数和除数倍数差，也即商。logN即为被除数和除数二进制的位数差，好比1011111/11，那么logN为7−2=5
空间复杂度: O(1)

1. class Solution {
2.     public int divide(int dividend, int divisor) {
3.         //如果除数是最小的int
4.         if(divisor == Integer.MIN_VALUE){
5.             return dividend == divisor?1:0;
6.         }
8.         //注意最小的int为-2^31,最大的int为2^31-1,如果商为2^31，越界，应返回2^31-1
9.         if(dividend == Integer.MIN_VALUE){
10.             if(divisor == 1){
11.                 return dividend;
12.             }
13.             if(divisor == -1){
14.                 return Integer.MAX_VALUE;
15.             }
16.         }
18.         //为了便于统一进行移位等操作，都转成正数来处理
19.         //如果dividend == Integer.MIN_VALUE，为了避免边界问题，先加上一个除数的绝对值，保证不越界
20.         //如果加上了绝对值，后面商的绝对值需要+1，所以设置一个标志位
21.         boolean plusOne = false;
22.         if(dividend == Integer.MIN_VALUE){
23.             dividend = dividend + (divisor>0?divisor:-divisor);
24.             plusOne = true;
25.         }
28.         //都转为正数处理
29.         boolean changeSymbol = false;
30.         if(divisor < 0){
31.             divisor = -divisor;
32.             changeSymbol = !changeSymbol;
33.         }
35.         if(dividend < 0){
36.             dividend = -dividend;
37.             changeSymbol = !changeSymbol;
38.         }
40.         //不断把除数进行左移，直到和被除数对齐
41.         int move = 0;
42.         int constant = (1<<30);
43.         while(divisor < dividend){
44.             //如果符号位后紧接的一位，也就数字位的最高位已经为1了，则不应该再左移了
45.             if( (divisor & constant) > 0){
46.                 break;
47.             }
48.             divisor <<= 1;
49.             move++;
50.         }
52.         // int move = Integer.numberOfLeadingZeros(divisor) - Integer.numberOfLeadingZeros(dividend);
53.         // divisor <<= move;
55.         
56.         //模拟手算除法的过程，无非是二进制而已。十进制每一位可以商0-9，二进制中只能商0或1
57.         int ans = 0;
58.         for(int i = move;i>=0;i--){
59.             if(dividend < divisor){
60.                 divisor >>= 1;
61.             }else{
62.                 ans += (1 << i);
63.                 dividend -= divisor;
64.                 divisor >>= 1;
65.             }
66.         }
68.         ans = plusOne?ans+1:ans;
69.         return changeSymbol?-ans:ans;
70.     }
71. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。