leetcode-两数相除

一、题目

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

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

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/divide-two-integers

二、思路

二分法递归，被除数每次都减去除数的两倍，直到被除数的数值小于除数的数值，不够减为止。这个迭代过程的次数，即是商。

十进制竖列式方法计算两个数的除法

二进制除法

三、代码实现

>folded main.go

func divide(dividend int, divisor int) int {
	if divisor == 0 {
		return math.MaxInt32
	}

	signdived, signdivor := 1, 1
	if dividend < 0 {
		dividend = -dividend
		signdived = -1
	}
	if divisor < 0 {
		divisor = -divisor
		signdivor = -1
	}

	res, _ := div(dividend, divisor, 1)

	if signdived != signdivor {
		res = -res
	}

	if res < math.MinInt32 || res > math.MaxInt32 {
		return math.MaxInt32
	}

	return res
}

func div(m, n, count int) (quo, rem int) {
	switch {
	case m < n:
		return 0, m
	case m >= n && m < n+n:
		return count, m - n
	default:
		quo, rem = div(m, n+n, count+count)
		if rem >= n {
			return quo + count, rem - n
		}
		return
	}
}