Divide Two Integers

分手后的思念是犯贱 2023-06-07 03:25 41阅读 0赞

# Divide Two Integers #

### 文章目录 ###

*  Divide Two Integers
 *   *  题目
     *  分析
     *  代码如下

## 题目 ##

Given two integers `dividend` and `divisor`, divide two integers without using multiplication, division and mod operator.  
Return the quotient after dividing `dividend` by `divisor`.  
The integer division should truncate toward zero.

**Example 1:**

Input: dividend = 10, divisor = 3
    Output: 3

**Example 2:**

Input: dividend = 7, divisor = -3
    Output: -2

**Note:**

*  Both dividend and divisor will be 32-bit signed integers.
 *  The divisor will never be 0.
 *  Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: \[ − 2 31 , 2 31 − 1 \] \[-2^\{31\}, 2^\{31\}-1\] \[−231,231−1\]. For the purpose of this problem, assume that your function returns  2 31 − 1 2^\{31\} - 1 231−1 when the division result overflows.

## 分析 ##

题目给出一个被除数和一个除数，这两个数都是`int`类型（有符号整数）。  
要求我们不用乘法、除法和模运算，求出这两者的商。  
并且给出的除数是不会是0，如果溢出了，则让结果为 2 32 − 1 2^\{32\} - 1 232−1。

最笨的解法就是不断将**被除数的绝对值**减去**除数的绝对值**，算出有多少个**除数**。但是当两个数的绝对值相差越大，时间复杂度越高。当除数是 ± 1 \\pm\{1\} ±1时，循环次数为被除数的绝对值。

另一种解法是模拟我们手算除法的过程来计算出其商。可以将两个数都转化为`String`类型，然后用`char[]`数组存起来，之后进行模拟计算。该方法需要将`int`转化为`String`类型，而且还需要自己实现`String`之间的加法和减法，比较麻烦，效率也不是很高。

第三种解法也是模拟手算除法的过程，只不过是计算二进制的除法而不是通常的十进制除法。相较于上一种解法，更加简洁，也比较简单。  
由于其取值范围是 \[ − 2 31 , 2 31 − 1 \] \[-2^\{31\}, 2^\{31\}-1\] \[−231,231−1\]，因此当被除数是 − 2 31 -2^\{31\} −231，除数是-1时，商是 2 31 2^\{31\} 231，会产生溢出；其他情况不会溢出（不考虑除数为0的情况）。

*  首先，需要将负数转化为整数，就是**取反加一**（`a = (~a) + 1`），但是当某一个数是 − 2 31 -2^\{31\} −231，即`0x80000000`时，取反加1之后仍然时`0x80000000`，我们这时候认为他是整数就可以了，在后面计算时需要稍加注意即可。
 *  然后当`转化后的被除数 - 转化后的除数 < 0`时，此时被除数小于除数，直接返回0。  
    需要注意的是，比较时不能使用`转化后的被除数 < 转化后的除数`，因为当其中一个数是`0x80000000`时，直接比较时会将其当作负数导致出错。例如`a = 0x80000000; b = 1`，此时`a - b = 0x7fffffff > 0`，和我们要的结果相符合。但是如果使用`a < b`进行比较，由于`a`是负数，这样得到的结果和我们想要的结果不符合。
 *  之后算出两个数的位数（例如：`0x00001000`总共有16位）。假设分别为`pos1`，`pos2`，假设临时商为`result`。取出被除数的前`pos2`bits，记为`tempDividend`。  
    **若`tempDividend - 除数 >= 0`**（注意：这里也不能使用`tempDividend > 除数`），则`result = (result < 1) + 1`，将`tempDividend`减去除数得到的结果右移一位，加上被除数下一位的值作为新的`tempDividend`。然后进行下一轮直到被除数没有未使用的`bit`。  
    **若`tempDividend - 除数 < 0`**，则`result = result < 1`。将`tempDividend`右移一位，加上被除数下一位的值作为新的`tempDividend`。然后进行下一轮直到被除数没有未使用的`bit`。
 *  最后根据结果的正负调整`result`即可。

**举个例子：**  
例如对于`10`除以`3`，转化为二进制数就是`1010`除以`11`，位数分别是`4`和`2`。  
第一次计算时`10 - 11 >= 0`为`false`，`result = reuslt << 1 = 0`，更新后的`tempDividend`为`101`。  
第二次计算时`101 - 11 >= 0`为`true`，`result = (result << 1) + 1 = 1`，更新后的`tempDividend`为`((101 - 11) << 1) + 0 = 100`。  
第三次计算时`100 - 11 >= 0`为`true`，`result = (result << 1) + 1 = 11`，此时被除数没有未使用的`bit`，循环到此结束。  
由于两个数都是正数，因此结果为正数`11`，转化为十进制就是3，于实际结果相符合。

## 代码如下 ##

class Solution { 
        public int divide(int dividend, int divisor) { 
        	boolean positive = true;  // 结果是不是正数
        	int result = 0;
        	int min = Integer.MIN_VALUE;  // 0x80000000
        	int max = Integer.MAX_VALUE;  // 0x7fffffff
        	if (dividend == min && divisor == -1) {   // 只有这一种情况会溢出
        		return max;
        	}
        	if (dividend >>> 31 == 1) {   // 无符号右移，判断是不是负数
        		positive = !positive;
        		dividend = (~dividend) + 1;
        	}
        	if (divisor >>> 31 == 1) {   // 无符号右移，判断是不是负数
        		positive = !positive;
        		divisor = (~divisor) + 1;
        	}
        	if (dividend - divisor < 0) {   // 被除数小于除数
        		return result;
        	}
        	int pos1 = findFirstOne(dividend);
        	int pos2 = findFirstOne(divisor);
        	int tempDividend = dividend >>> (pos1 - pos2);
        	int res;
        	if (tempDividend - divisor >= 0) { 
        		result = 1;
        		res = tempDividend - divisor;
        	} else { 
    			result = 0;
    			res = tempDividend;
    		}
        	for (int i = pos1 - pos2 - 1; i >= 0; i--) { 
        		tempDividend = (res << 1) + ((dividend & (1 << i)) >> i);
        		if (tempDividend - divisor >= 0) { 
        			result = (result << 1) + 1;
        			res = tempDividend - divisor;
        		} else { 
    				result = result << 1;
    				res = tempDividend;
    			}
        	}
        	if (positive) { 
        		return result;
        	} else { 
    			return (~result) + 1;
    		}
        }
        /** * @param num * @return 第一个非零bit的位置，最高位为31，最低位为0 */
        private int findFirstOne(int num) { 
        	int pos = 0;
        	while (num > 0) { 
        		num = num << 1;
        		pos++;
        	}
        	return 31 - pos;
        }
    }