引言
题目链接：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 } } |
