LeetCode: 29. Divide Two Integers

引言

题目链接：https://leetcode.com/problems/divide-two-integers/

题目大意

给定一个除数和被除数，要求不使用除法、乘法以及取模操作计算。返回两个数做除法的商（结果取整数，就相当于两个int做计算）

Hint

------------------
1. 被除数和除数都是32位整数（int32）
2. 除数永远不可能为0
3. 本题运行环境只能存储int32类型，如果计算结果溢出，返回2^31 − 1

• Example

题解

题目规定了无法使用乘除法取模运算，因此就只有考虑加减法和位运算了。

假设商为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++版本

go版本