首页 > 代码库 > LeetCode --- 29. Divide Two Integers
LeetCode --- 29. Divide Two Integers
题目链接：Divide Two Integers
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
这道题的要求是在不使用乘法、除法、取模运算的前提下实现两个整数相除。如果溢出，返回MAX_INT。
这道题的直接思路是用被除数不断减去除数，直到为0。这种方法的迭代次数是结果的大小，即比如结果为n，算法复杂度是O(n)。
可以采用位运算进行优化，即模拟计算机上的除法运算。将整数转化成二进制形式，即num = a0*2^0 + a1*2^1 + a2*2^2 + ... + an*2^n。基于以上这个公式以及左移一位相当于乘以2，可以先让除数左移直到大于被除数之前得到一个最大的基数。然后每次用被除数去减去这个基数，同时结果增加2^k。接下来继续重新左移除数左移迭代，直到被除数不大于除数为止。因为这个方法的迭代次数是按2的幂直到结束，所以时间复杂度为O(logn)。
值得注意的地方，主要就是处理符号和溢出问题。对于溢出问题，可以先采用long long进行计算，也可以在移位前判断移位后是否溢出。
时间复杂度：O(logn)
空间复杂度：O(1)
1 class Solution
2 {
3 public:
4 int divide(int dividend, int divisor)
5 {
6 int sign = (dividend < 0) ^ (divisor < 0) ? - 1 : 1;
7 long long res = 0, m = abs((long long)dividend), n = abs((long long)divisor);
8 while(m >= n)
9 {
10 long long t = n, i = 1;
11 while(t << 1 < m)
12 {
13 t <<= 1;
14 i <<= 1;
15 }
16 m -= t;
17 res += i;
18 }
19 if(sign < 0)
20 res = -res;
21 return res > INT_MAX ? INT_MAX : res;
22 }
23 };转载请说明出处：LeetCode --- 29. Divide Two Integers
LeetCode --- 29. Divide Two Integers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。