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

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

### 题目

``*``
``/``
``%``

### 分析

``基于减法实现除法``

``*``
``自己加自己``
``value+=value``

• 结果溢出
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;

}
}
``````