实现除法操作

朱雀 2022-01-20 07:23 217阅读 0赞

### 前文 ###

1.  一道算法题，涉及到了二进制的位操作，借这个机会整理一下[相关的知识点][Link 1]，并且在这道算法题中进行了实践
2.  本文的解法来自于该算法题的[一篇讨论][Link 2]。

--------------------

### 一、[算法题介绍][Link 3] ###

对除数和被除数实现除法运算，其中不使用乘法、除法和求余操作，返回对应的商。如，  
Input: dividend = 10, divisor = 3  
Output: 3

### 解法1：暴力解法 ###

class Solution
    {
        public int divide(int dividend, int divisor)
        {
    	    //定义除法，被除数是最小值，除以-1时，是最大值
    	    if(dividend == Integer.MIN_VALUE && divisor == -1)
    		return Integer.MAX_VALUE;
    	    //^运算符，只有不同时，才为true ; sign定义商是否为负数  
    	    int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
    	    int result = 0;
    	    //取除数和被除数的正数形式
    	    long x = Math.abs((long)dividend);
    	    long y = Math.abs((long)divisor);
    
    	    //统计被除数共减去多少个除数，即为商
    	    while(x >= y)
    	    {
    		x -= y;
    		result++;
    	     }
    	     return sign > 0 ? result : -result;
        }
    }
    复制代码

1.  暴力解法主要是通过不断循环将y（除数）从x（被除数）中减去，直到x<y. x减去y的次数就是商，而最后剩下的小于y的部分就是余数。暴力解法的时间复杂度很高，比如说，当x=231\-1,y=1时，需要循环231\-1次。

*  时间复杂度：O(x),x是被除数。
 *  空间复杂度：O(1)。

### 解法2：除数左移位累加 ###

class Solution
    {
        public int divide(int dividend, int divisor)
        {
            if(dividend == Integer.MIN_VALUE && divisor == -1)
                return Integer.MAX_VALUE;
            int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
            int result = 0;
            long x = Math.abs((long)dividend);
            long y = Math.abs((long)divisor);
            while(x >= y)
            {
                int shift = 1;
                //将y持续向左移位，相当于y*2^(shift);
                //当y*2^(shift)< x <y*2^(shift+1)时，循环结束
                while(x >= (y << shift))
                {
                    shift++;
                }
                x -= y << (shift - 1);
                //相当于x = y*2^(shift)+y*2^(shift-n)+.....+y*2^(0) + m;m是余数
                result += 1 << (shift - 1);
            }
            return sign > 0 ? result : -result;
        }
    }
    复制代码

1.  这个方法，是计算最大的k,使得y\*2k<=x，然后将y\*2k从x中减去，将2k加到商里面。比如说， 如果x= (1011)2，y=(10)2，那么因为2\*22<= 11而且2\*23>11 所以k=2。所以，我们将 (1011)2减去 (1000)2得到 (11)2，然后，将2k=22=(100)2加到商中，然后将x更新为(11)2继续运算。
2.  使用y\*2k的优势在于，可以使用非常高效的移位操作，而且每次循环后，最差的情况下，x都会变为原来的一半。如果n是x/y的商的位数，那么总共需要n次循环。子循环中每次通过循环k次来找到y\*2k的最大的k，因此：

*  时间复杂度：O(n2),n是x/y的商的位数。
 *  空间复杂度：O(1)。

### 解法3：除数左移位递减 ###

class Solution
    {
        public int divide(int dividend, int divisor)
        {
               if(dividend == Integer.MIN_VALUE && divisor == -1)
                   return Integer.MAX_VALUE;
            
               int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
               int result = 0;
               int power = 32;
              //long是8字节，64位；int是4字节，32位
               long x = Math.abs((long)dividend);
               long y = Math.abs((long)divisor);
            
               while(x >= y)
               {
                   //将y*2^32增加到最大，然后逐步减小，靠近x
                   //y*2^power<x时结束
                   while((y << power) > x)
                   {
                       //每次只需要执行有限步就能找到power，不像前面中的方法，是执行O(n)步才能找到
                       power--;
                   }
                   x -= y << power;
                   result += 1 << power;
                   
               }
               return sign > 0 ? result : -result;
       }
    }
    复制代码

1.在每次循环中找到最大的k的最好的方式就是认识到k其实是在不断缩小的。因此，我们不需要在每次子循环的时候都检验一下21，22，23......是否小于或者等于x，我们可以在找到最大的k后，直接在后面的每次循环中检验x和2k-1，2k-2，2k-3....的关系。  
2. 我们可以继续之前的例子。商为(100)2后，我们继续计算(11)2。因为y\*2k<=x的最大k是0，所以我们把20=(1)2加到商里，因此商就变成了(101)2。然后我们继续算法，因此(1)2<y，所以算法结束。最后，我们可以得到，x= (1011)2，y=(10)2相除，商为(101)2，余数为(1)2。

*  时间复杂度：O(n),n是x/y的商的位数。
 *  空间复杂度：O(1)

[Link 1]: https://juejin.im/post/5c8de6fd6fb9a071050495d1
[Link 2]: https://link.juejin.im?target=https%3A%2F%2Fleetcode.com%2Fproblems%2Fdivide-two-integers%2Fdiscuss%2F246094%2FJava-Solutions
[Link 3]: https://link.juejin.im?target=https%3A%2F%2Fleetcode.com%2Fproblems%2Fdivide-two-integers%2F