【刷题笔记】29. Divide Two Integers

题目

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

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

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

Note:

• Both dividend and divisor will be 32-bit signed integers.
• The divisor will never be 0.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 2^31 − 1 when the division result overflows.

题目大意

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。

说明:

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

解题思路

• 给出除数和被除数，要求计算除法运算以后的商。注意值的取值范围在 [−2^31, 2^31 − 1] 之中。超过范围的都按边界计算。
• 这一题可以用二分搜索来做。要求除法运算之后的商，把商作为要搜索的目标。商的取值范围是 [0, dividend]，所以从 0 到被除数之间搜索。利用二分，找到(商 + 1 ) * 除数 > 被除数并且 商 * 除数 ≤ 被除数 或者 (商+1)* 除数 ≥ 被除数并且商 * 除数 < 被除数的时候，就算找到了商，其余情况继续二分即可。最后还要注意符号和题目规定的 Int32 取值范围。
• 二分的写法常写错的 3 点：
  1. low ≤ high (注意二分循环退出的条件是小于等于)
  2. mid = low + (high-low)>>1 (防止溢出)
  3. low = mid + 1 ; high = mid - 1 (注意更新 low 和 high 的值，如果更新不对就会死循环)

参考代码

package leetcode

import (
	"math"
)

// 解法一 递归版的二分搜索
func divide(dividend int, divisor int) int {
	sign, res := -1, 0
	// low, high := 0, abs(dividend)
	if dividend == 0 {
		return 0
	}
	if divisor == 1 {
		return dividend
	}
	if dividend == math.MinInt32 && divisor == -1 {
		return math.MaxInt32
	}
	if dividend > 0 && divisor > 0 || dividend < 0 && divisor < 0 {
		sign = 1
	}
	if dividend > math.MaxInt32 {
		dividend = math.MaxInt32
	}
	// 如果把递归改成非递归，可以改成下面这段代码
	// for low <= high {
	// 	quotient := low + (high-low)>>1
	// 	if ((quotient+1)*abs(divisor) > abs(dividend) && quotient*abs(divisor) <= abs(dividend)) || ((quotient+1)*abs(divisor) >= abs(dividend) && quotient*abs(divisor) < abs(dividend)) {
	// 		if (quotient+1)*abs(divisor) == abs(dividend) {
	// 			res = quotient + 1
	// 			break
	// 		}
	// 		res = quotient
	// 		break
	// 	}
	// 	if (quotient+1)*abs(divisor) > abs(dividend) && quotient*abs(divisor) > abs(dividend) {
	// 		high = quotient - 1
	// 	}
	// 	if (quotient+1)*abs(divisor) < abs(dividend) && quotient*abs(divisor) < abs(dividend) {
	// 		low = quotient + 1
	// 	}
	// }
	res = binarySearchQuotient(0, abs(dividend), abs(divisor), abs(dividend))
	if res > math.MaxInt32 {
		return sign * math.MaxInt32
	}
	if res < math.MinInt32 {
		return sign * math.MinInt32
	}
	return sign * res
}

func binarySearchQuotient(low, high, val, dividend int) int {
	quotient := low + (high-low)>>1
	if ((quotient+1)*val > dividend && quotient*val <= dividend) || ((quotient+1)*val >= dividend && quotient*val < dividend) {
		if (quotient+1)*val == dividend {
			return quotient + 1
		}
		return quotient
	}
	if (quotient+1)*val > dividend && quotient*val > dividend {
		return binarySearchQuotient(low, quotient-1, val, dividend)
	}
	if (quotient+1)*val < dividend && quotient*val < dividend {
		return binarySearchQuotient(quotient+1, high, val, dividend)
	}
	return 0
}

// 解法二 非递归版的二分搜索
func divide1(divided int, divisor int) int {
	if divided == math.MinInt32 && divisor == -1 {
		return math.MaxInt32
	}
	result := 0
	sign := -1
	if divided > 0 && divisor > 0 || divided < 0 && divisor < 0 {
		sign = 1
	}
	dvd, dvs := abs(divided), abs(divisor)
	for dvd >= dvs {
		temp := dvs
		m := 1
		for temp<<1 <= dvd {
			temp <<= 1
			m <<= 1
		}
		dvd -= temp
		result += m
	}
	return sign * result
}

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}