# 引言

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

# 题目大意

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

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

Input: dividend = 7, divisor = -3
Output: -2

# 题解

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

假设商为 s, 余数为 r, 则有dividend=divisors+rdividend=divisor*s+r

一个比较朴素的想法就是一直用被除数 (dividend) 减去除数 (divisor), 直到某一次结果小于除数的时候,总共操作的减法次数就是商 s 的值。但是这样当被除数很大,除数很小的时候,进行减法操作次数会很多,运算就会超时。

可行的方法就是减少做减法的次数,有如下操作过程

s=20+21+...2ks=2^0+2^1+...2^k

dividend=divisor(20+21+...+2k)+rdividend=divisor∗(2^0+2^1+...+2^k)+r

每一次确定当前等式的2k2^k, dividenddividend 减去dicisor2kdicisor*2^k, 2k2^k 等于减去这个数等效的做减法次数,至于求解2k2^k, 一个高效的方法可以通过位移运算实现,即原等式与如下等式等价

dividend=divisor<<0+divisor<<1+...+divisor<<k+rdividend=divisor<<0+divisor<<1+...+divisor<<k+r

# 复杂度

时间复杂度 O((logn)^2) , n 等于被除数的位数

空间复杂度 O(1)

# AC 代码

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
	}
}
更新于 阅读次数