29. 两数相除

🟠   🔖  位运算 数学  🔗 LeetCode

题目

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return _the quotient after dividing _dividend bydivisor.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For this problem, if the quotient is strictly greater than 2^31 - 1, then return 2^31 - 1, and if the quotient is strictly less than -2^31, then return -2^31.

Example 1:

Input: dividend = 10, divisor = 3

Output: 3

Explanation: 10/3 = 3.33333.. which is truncated to 3.

Example 2:

Input: dividend = 7, divisor = -3

Output: -2

Explanation: 7/-3 = -2.33333.. which is truncated to -2.

Constraints:

• -2^31 <= dividend, divisor <= 2^31 - 1
• divisor != 0

题目大意

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

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

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

**注意：**假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−2^31, 2^31 − 1] 。本题中，如果商 严格大于 2^31 − 1 ，则返回 2^31 − 1 ；如果商 严格小于 -2^31 ，则返回 -2^31 。

解题思路

1. 处理符号问题：

   • 首先判断结果的符号：如果 dividend 和 divisor 中只有一个是负数，结果是负的，否则结果为正的。
   • 可以通过将 dividend 和 divisor 取绝对值来处理后续的无符号整数运算。

2. 倍增法：

   • 为了模拟除法，我们可以用减法模拟。直接进行减法会超时，因此采用倍增法提高效率。
   • 基本思想是将除数（divisor）不断翻倍（即乘以 2），直到超过被除数（dividend）。这相当于不断减去更大的除数倍数（2 的幂次）来逼近结果。
   • 每次当倍增的除数能从被除数中减去时，记录下对应的倍数（即商的部分），直到被除数小于除数为止。

3. 处理边界情况：

   • 如果 divisor == 0，不能除零，直接返回。
   • 如果 dividend == -2^31 且 divisor == -1，会导致溢出，这种情况下直接返回 2^31 - 1（即 2147483647）。

4. 返回结果：

   • 根据之前判断的符号情况，返回商的正负值。

复杂度分析

• 时间复杂度：O(logn)，其中 n 是 dividend 的大小。每次倍增都将被除数缩小到原来的一半，故时间复杂度为对数级别。
• 空间复杂度：O(1)，除了存储变量外，所需的额外空间是常数级的。

代码

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function (dividend, divisor) {
	// 处理特殊情况

	if (divisor == 0) return Infinity; // 除数为 0
	if (dividend == -Math.pow(2, 31) && divisor == -1) return Math.pow(2, 31) - 1; // 溢出情况

	// 判断结果符号
	let isNegative = dividend > 0 !== divisor > 0;
	// 取绝对值，处理负数问题
	dividend = Math.abs(dividend);
	divisor = Math.abs(divisor);

	let res = 0;
	// 倍增法
	while (dividend >= divisor) {
		let temp = divisor,
			multi = 1;
		while (dividend >= 2 * temp) {
			temp *= 2; // 除数翻倍
			multi *= 2; // 倍数也翻倍
		}
		dividend -= temp; // 减去翻倍后的除数
		res += multi; // 商加上相应的倍数
	}

	// 返回结果，处理符号
	return isNegative ? -res : res;
};