[leetcode] 29. Divide Two Integers

[leetcode] 29. Divide Two Integers

Description

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 = 3Output: 3

Example 2:

Input: dividend = 7, divisor = -3Output: -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]. For the purpose of this problem, assume that your function returns 2^31 − 1 when the division result overflows.

分析

题目的意思是：给你一个除数和一个被除数，不能用乘除，求余数运算，求出结果。

可以采用位运算进行优化，即模拟计算机上的除法运算。将整数转化成二进制形式，即num = a02^0 + a12^1 + a22^2 + … + an2^n。 基于以上这个公式以及左移一位相当于乘以2，可以先让除数左移直到大于被除数之前得到一个最大的基数。然后每次用被除数去减去这个基数，同时结果增加2^k。接下来继续重新左移除数左移迭代，直到被除数不大于除数为止。因为这个方法的迭代次数是按2的幂直到结束，所以时间复杂度为O(logn)。

时间复杂度：O(logn)空间复杂度：O(1)

代码

class Solution {public: int divide(int dividend, int divisor) { if(divisor==0||(dividend==INT_MIN&&divisor==-1)) return INT_MAX; long long m=abs((long long)dividend); long long n=abs((long long)divisor); int sign=1; if(dividend<0^divisor<0){ sign=-1; } if(n==1) return m*sign; long long res=0; while(m>=n){ long long t=n,p=1; while(m>=(t<<1)){ t<<=1; p<<=1; } res+=p; m-=t; } return res*sign; }};

参考文献

​​LeetCode — 29. Divide Two Integers​​​​[LeetCode] Divide Two Integers 两数相除​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。