LeetCode_29: Divide Two Integers - LeetCode

# 引言

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

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

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

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)

c++ 版本

	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 版本

	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
	}
	}