【剑指Offer】1.整数除法([sword finger offer] 1. Integer division)

创建时间: November 22, 2021 2:54 PM
最后编辑时间: November 22, 2021 4:21 PM
标签: 位运算, 数学
网址: https://leetcode-cn.com/problems/xoh6Oh/
难度: 简单

题目

输入2个int型整数,它们进行除法计算并返回商,要求不得使用乘号、除号及求余符号。当发生溢出时,返回最大的整数值。假设除数不为0。例如,输入15和2,输出15/2的结果,即7。

*
/
%

分析

这个题目限制我们不能使用乘号和除号进行运算。一个直观的解法是。例如,为了求得15/2的商,可以不断地从15里减去2,当减去7个2之后余数是1,此时不能再减去更多的2,因此15/2的商是7。我们可以用一个循环实现这个过程。

基于减法实现除法

但这个直观的解法存在一个问题。当被除数很大但除数很小时,减法操作执行的次数会很多。例如,求\((2^{31}-1 )/1\),减1的操作将执行\(2^{31}-1\)次,需要很长的时间。如果被除数是\(n\),那么这种解法的时间复杂度为\(O(n)\)。

我们需要对这种解法进行优化。可以将上述解法稍做调整。当被除数大于除数时,继续比较判断被除数是否大于除数的2倍,如果是,则继续判断被除数是否大于除数的4倍、8倍等。如果被除数最多大于除数的2k倍,那么将被除数减去除数的2k倍,然后将剩余的被除数重复前面的步骤。由于每次将除数翻倍,因此优化后的时间复杂度是\(O(logn)\)。(:这里减去除数的2k倍,而不是k倍,是因为本题ban掉了乘号 ,因此要实现被除数减去除数的倍数,只能通过将除数通过的方式进行翻倍,即 ,所以倍数是2k倍,即2的整数倍。)

*
自己加自己
value+=value

下面以15/2为例讨论计算的过程。15大于2,也大于2的2倍(即4),还大于2的4倍(即8),但小于2的8倍(即16)。于是先将15减去8,还剩余7。由于减去的是除数的4倍,减去这部分对应的商是4。接下来对剩余的7和除数2进行比较,7大于2,大于2的2倍(即4),但小于2的4倍(即8),于是将7减去4,还剩余3。这一次减去的是除数2的2倍,对应的商是2。然后对剩余的3和除数2进行比较,3大于2,但小于2的2倍(即4),于是将3减去2,还剩余1。这一次减去的是除数的1倍,对应的商是1。最后剩余的数字是1,比除数小,不能再减去除数了。于是15/2的商是4+2+1,即7。

一些细节

  • 结果溢出
    java中int的取值范围是\([-2^{31},2^{31}-1]\),因此只有一种情况下,结果才会溢出,即\(-2^{31}/(-1)=2^{31}\)
  • int的最小值
    可以用Integer.MIN_VALUE 表示,也可以用0x80000000 表示(最高位是符号位,1表示负数,其他位全为0,根据补码可以计算出值为\(-2^{31}\))
  • 正负号
    同号相除为正,异号相除为负。先同号相除,再定正负。
    思考:使用正数相除还是负数相除?
    答:负数相除,因为负数最小值的绝对值比正数大,因此负数转正数可能会溢出。使用负数相除时,采用的方法是基于加法实现除法 ,与前面的例子类似。

代码

class Solution {
    public int divide(int a, int b) {
        //唯一溢出的情况: -2^31 / -1 =2^31 ,溢出
        if(a==Integer.MIN_VALUE && b==-1)return Integer.MAX_VALUE;
        //被除数为0,结果也为0
        if(a==0)return 0;
        //同号相除为正,异号为负
        int negative=2;
        if(a>0){
            a=-a;
            negative--;
        }
        if(b>0){
            b=-b;
            negative--;
        }
        //这里将运算双方转为负数相除,因为负数的绝对值比正数的绝对值大1,所有运算范围比正数大
        int res=divideNegative(a,b);
        return negative==1?-res:res;

    }
    //定义两个负数的除法运算
    public int divideNegative(int a,int b){
        //存放结果
        int res=0;
        //基于加法实现负数的除法操作
        while(a<=b){
            //用value实现除数b的不断翻倍
            int value=b;
            //times是除数b的倍数
            int times=1;
            //value>=0xc0000000是为了防止value+value溢出,0xc0000000等于Integer.MIN_VALUE/2
            while(value>=0xc0000000 && a<=value+value){
                times+=times;
                value+=value;
            }
            res+=times;
            a-=value;
        }
        return res;

    }
}
————————

Created: November 22, 2021 2:54 PM
Last edited: November 22, 2021 4:21 PM
Labels: bit operations, mathematics
website: https://leetcode-cn.com/problems/xoh6Oh/
Difficulty: simple

subject

Enter two int integers, which perform division calculation and return quotient. It is required that multiplication sign, division sign and remainder sign shall not be used. Returns the maximum integer value when overflow occurs. Assume that the divisor is not 0. For example, input 15 and 2 and output the result of 15 / 2, that is, 7.

*
/
%

analysis

This problem restricts us from using multiplication and division signs. An intuitive solution is. For example, in order to obtain the quotient of 15 / 2, you can constantly subtract 2 from 15. When you subtract 7 2, the remainder is 1. At this time, you can’t subtract more 2, so the quotient of 15 / 2 is 7. We can implement this process with a loop.

基于减法实现除法

But there is a problem with this intuitive solution. When the divisor is large but the divisor is small, the subtraction operation will be performed many times. For example, to find \ ((2 ^ {31} – 1) / 1 \) and subtract 1 will execute \ (2 ^ {31} – 1 \) times, which takes a long time. If the divisor is \ (n \), the time complexity of this solution is \ (O (n) \).

We need to optimize this solution. The above solution can be slightly adjusted. When the divisor is greater than the divisor, continue to compare and judge whether the divisor is greater than 2 times of the divisor. If so, continue to judge whether the divisor is greater than 4 times or 8 times of the divisor. If the divisor is greater than 2K times the divisor at most, subtract 2K times the divisor from the divisor, and then repeat the previous steps for the remaining divisor. Since the divisor is doubled each time, the optimized time complexity is \ (O (logn) \). (< strong > note < / strong >: 2K times of the divisor is subtracted here, not k times, because the multiplier sign is missing in this question ban. Therefore, to realize the multiple of the divisor subtracted from the divisor, you can only double it by passing the divisor, that is, so the multiple is 2K times, that is, an integer multiple of 2.)

*
自己加自己
value+=value

Next, take 15 / 2 as an example to discuss the calculation process. 15 is greater than 2, greater than 2 times (i.e. 4), greater than 4 times (i.e. 8) of 2, but less than 8 times (i.e. 16) of 2. So first subtract 8 from 15, leaving 7. Since you subtract four times the divisor, the quotient corresponding to subtracting this part is 4. Next, compare the remaining 7 with divisor 2. 7 is greater than 2, greater than 2 times (i.e. 4), but less than 4 times (i.e. 8) of 2, so subtract 4 from 7 and 3 remains. This time you subtract twice the divisor 2, and the corresponding quotient is 2. Then compare the remaining 3 with the divisor 2. 3 is greater than 2 but less than 2 times (i.e. 4), so subtract 2 from 3 and 1 remains. This time you subtract 1 times the divisor, and the corresponding quotient is 1. The last remaining number is 1, which is smaller than the divisor. You can’t subtract the divisor. So the quotient of 15 / 2 is 4 + 2 + 1, that is, 7.

< strong > some details < / strong >

  • Result overflow
    The value range of int in Java is \ ([- 2 ^ {31}, 2 ^ {31} – 1] \), so the result will overflow only in one case, that is \ (- 2 ^ {31} / (- 1) = 2 ^ {31} \)
  • Minimum value of int
    You can use integer.min_ Value can also be represented by 0x80000000 (the highest bit is a sign bit, 1 represents a negative number, and all other bits are 0. The value can be calculated as \ (- 2 ^ {31} \) according to the complement)
  • Sign
    The division of the same sign is positive and the division of the different sign is negative. First divide by the same sign, and then determine the positive and negative.
    Think: divide by positive or negative numbers?
    A: negative numbers are divided by negative numbers. Because the absolute value of the minimum value of negative numbers is greater than positive numbers, the conversion of negative numbers to positive numbers may overflow. When using negative number division, the method used is to implement division based on addition, which is similar to the previous example.

code

class Solution {
    public int divide(int a, int b) {
        //唯一溢出的情况: -2^31 / -1 =2^31 ,溢出
        if(a==Integer.MIN_VALUE && b==-1)return Integer.MAX_VALUE;
        //被除数为0,结果也为0
        if(a==0)return 0;
        //同号相除为正,异号为负
        int negative=2;
        if(a>0){
            a=-a;
            negative--;
        }
        if(b>0){
            b=-b;
            negative--;
        }
        //这里将运算双方转为负数相除,因为负数的绝对值比正数的绝对值大1,所有运算范围比正数大
        int res=divideNegative(a,b);
        return negative==1?-res:res;

    }
    //定义两个负数的除法运算
    public int divideNegative(int a,int b){
        //存放结果
        int res=0;
        //基于加法实现负数的除法操作
        while(a<=b){
            //用value实现除数b的不断翻倍
            int value=b;
            //times是除数b的倍数
            int times=1;
            //value>=0xc0000000是为了防止value+value溢出,0xc0000000等于Integer.MIN_VALUE/2
            while(value>=0xc0000000 && a<=value+value){
                times+=times;
                value+=value;
            }
            res+=times;
            a-=value;
        }
        return res;

    }
}