29. Divide Two Integers

发表于 | 分类于

每日一题 2019 - 03 - 13

题目：

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:

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

Example 2:

1
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: . For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

解法：

这个题让我们不使用乘法、除法、取模的方法找出两个数字相除的结果。

最开始我的想法是使用循环相加的方法，但发现会超时，还是需要另寻道路，所以参考了几个dalao的解法，其中最值得称赞的就是位运算的方法，也即减少被除数，左移除数，商求加法，举个例子：

例如：被除数为 9 ，除数为 2 ，求商可以这么操作，设指针p = 当前循环求出的商的以为结果,t = 当前循环除数移位的结果

  • 第一趟被除数 = 9 ，除数 = 2 ，由于 9 > 2 << 1 ，所以 p << 1 ，也即 p = 2 ，所以此时商 + p = 商 + 2 = 2，结束之后余下的被除数为 9 - 4 = 5 ；
  • 第二趟被除数 = 5 ，除数 = 2 ，由于 5 > 2 << 1 ，所以 p << 1 ，也即 p = 2 ，所以此时商 + p = 商 + 2 = 4，结束之后余下的被除数为 5 - 4 = 1 ；
  • 第三趟被除数 = 1 ，除数 = 2 ，由于 1 < 2 << 1 且 1 < 2，所以 p = 0 ，也即被除数小于除数无法再增加商的大小 ，所以跳出循环，得到最终结果商 = 4；

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int divide(int dividend, int divisor) {
        if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX;//因为带符号整数的范围为-2^n~2^n-1，故存在一种特殊情况
        
        //取两数的绝对值
		 long long m = abs((long long)dividend), n = abs((long long)divisor), res = 0;
		 int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;//注意此处异或的作用
		 if (n == 1) return sign == 1 ? m : -m;
 
		while (m >= n) {
			long long t = n, p = 1;
			while (m >= (t << 1)) {
				p <<= 1;
				t <<= 1;
			}
			res += p;
			m -= t;
		}
		return sign > 0 ? res : -res;
    }
};
0%
undefined