[0029] 两数相除

• GitHub
• http://leetcode.xuezhisd.top/post/294b0aae.html
• https://leetcode.com/problems/divide-two-integers
• https://leetcode-cn.com/problems/divide-two-integers

题目描述

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:

输入: dividend = 10, divisor = 3
输出: 3

示例 2:

输入: dividend = 7, divisor = -3
输出: -2

说明:

• 被除数和除数均为 32 位有符号整数。
• 除数不为 0。
• 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2³¹,  2³¹ − 1]。本题中，如果除法结果溢出，则返回 2³¹ − 1。

Related Topics

数学

二分查找

题目解析

• 本题是一道模拟题

不确定性

方法一：位移运算法

分析

• 首先会想到利用减法，但是此方法速度过慢，例如200/3，需要执行66次减法
• 可以使用位移法，每次将除数放大2倍，例如200/3，则会变为200/(3*2^x^)，这一步时只需要执行6次左移操作

思路

• 将除数通过左移运算符放大2倍，直到成为小于被除数的最大数值
• 不断放大的总倍数则加入到商中，并将被除数减去前一步求解的最大数值
• 重复执行上述步骤，直到最后余下的数值小于除数

注意

• 测试样例中的除数可能会存在-2^31^，当进行绝对值运算时，我们需要使用long来保存，因为int的最大值为2^31^

知识点

• 位移运算

复杂度

• 时间复杂度 O(log(n))
• 空间复杂度 O(1)

代码

int divide(int dividend, int divisor) {
	long ans = 0, up = abs(dividend), down = abs(divisor);
	while (up >= down){
		long count = 1, base = down;
		while (up > (base << 1)){
			count <<= 1;
			base <<= 1;
		}
		ans += count;
		up -= base;
	}
	ans = ((dividend < 0) ^ (divisor < 0)) ? -ans : ans;
	return (ans > INT_MAX || ans < INT_MIN) ? INT_MAX : ans;
}

方法二：[算法名称]

分析

思路

注意

知识点

复杂度

代码

//

相关题目