引言
题目链接:https://leetcode.com/problems/divide-two-integers/
题目大意
给定一个除数和被除数,要求不使用除法、乘法以及取模操作计算。返回两个数做除法的商(结果取整数,就相当于两个int做计算)
- Example
1 2 3 4 5 |
Input: dividend = 10, divisor = 3 Output: 3 Input: dividend = 7, divisor = -3 Output: -2 |
题解
题目规定了无法使用乘除法取模运算,因此就只有考虑加减法和位运算了。
假设商为s,余数为r,则有$dividend=divisor*s+r$
一个比较朴素的想法就是一直用被除数($dividend$)减去除数($divisor$),直到某一次结果小于除数的时候,总共操作的减法次数就是商s的值。但是这样当被除数很大,除数很小的时候,进行减法操作次数会很多,运算就会超时。
可行的方法就是减少做减法的次数,有如下操作过程
$s=2^0+2^1+...2^k$
$dividend=divisor∗(2^0+2^1+...+2^k)+r$
每一次确定当前等式的$2^k$,$dividend$减去$dicisor*2^k$,$2^k$等于减去这个数等效的做减法次数,至于求解$2^k$,一个高效的方法可以通过位移运算实现,即原等式与如下等式等价
$dividend=divisor<<0+divisor<<1+...+divisor<<k+r$
复杂度
时间复杂度 O((logn)^2), n等于被除数的位数
空间复杂度 O(1)
AC代码
c++版本
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
class Solution { public: int divide(int dividend, int divisor) { if (0 == divisor || (INT32_MIN == dividend && -1 == divisor)) { return INT32_MAX; } if (1 == divisor) { return dividend; } bool negative = (dividend > 0) ^ (divisor > 0); int ret = 0; long ldividend = labs(dividend); long ldivisor = labs(divisor); while (ldividend >= ldivisor) { long k = ldivisor; long r = 1; while (ldividend >= (k << 1)) { k <<= 1; r <<= 1; } ldividend -= k; ret += r; } return true == negative ? -ret : ret; } }; |
go版本
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
const ( INT32_MAX = int(^uint32(0) >> 1) INT32_MIN = ^INT32_MAX ) func labs(x int64) int64 { if x < 0 { return -x } return x } func divide(dividend int, divisor int) int { if 0 == divisor || (INT32_MIN == dividend && divisor == -1) { return INT32_MAX } else if 1 == divisor { return dividend } ret := 0 ldividend, ldivisor := labs(int64(dividend)), labs(int64(divisor)) for ldividend >= ldivisor { k, r := ldivisor, 1 for ldividend >= (k << 1) { k <<= 1 r <<= 1 } ret += r ldividend -= k } if (dividend >= 0 && divisor >= 0) || (dividend < 0 && divisor < 0) { return ret } else { return -ret } } |