五一假期，外面的世界人山人海，而在家刷题成了一种不错的休闲方式。我刚好开始写这道题：

给定两个整数`被除数`和`除数`，在不使用乘法、除法和取模运算符的情况下，实现整数除法。整数除法应该向零截断，即去除其小数部分。例如，`8.345`应该截断为`8`，`-2.7335`应该截断为`-2`。

返回`被除数`除以`除数`后的**商**。

**注意：**假设我们只能处理32位有符号整数范围内的整数：`[−231, 231 − 1]`。对于此问题，如果商**严格大于**`231 - 1`，则返回`231 - 1`，如果商**严格小于**`-231`，则返回`-231`。

**示例1：**

输入：被除数 = 10，除数 = 3
输出：3
解释：10/3 = 3.33333.. 截断为3。

**示例2：**

输入：被除数 = 7，除数 = -3
输出：-2
解释：7/-3 = -2.33333.. 截断为-2。

**约束条件：**

- `-231 <= 被除数, 除数 <= 231 - 1` - `除数 != 0`

理解题目要求，不能使用乘法、除法和取模运算符来计算两个给定整数的商。这时我想到可以利用移位操作来实现。

虽然我在工作多年，但实际项目中使用移位操作的情况并不多。

逻辑移位：

- 逻辑移位将位向左或向右移动，并在空位填充零。 - 在左逻辑移位（<<）中，位向左移动，从右侧填充零。 - 在右逻辑移位（>>）中，位向右移动，从左侧填充零。

简单来说，如果1<<2，就是1乘以2的2次方，以此类推。

因此，我的解决方案很明确，处理好被除数和除数的符号，然后通过循环内使用移位操作来计算商：

func divide(dividend int, divisor int) int {
	quotient := 0
	maxInt := math.MaxInt32
	minInt := math.MinInt32
	if divisor == 0 || (dividend == minInt && divisor == -1) {
		return maxInt
	}

	// 确定商的符号
	sign := -1
	if (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0) {
		sign = 1
	}

	// 将被除数和除数转换为正数
	positiveDividend, positiveDivisor := int(math.Abs(float64(dividend))), int(math.Abs(float64(divisor)))

	for positiveDividend >= positiveDivisor {
		shift := 0
		for positiveDividend >= (positiveDivisor << shift) {
			shift += 1
		}

		quotient += (1<< (shift - 1))
		positiveDividend -= (positiveDivisor << (shift - 1))
	}
	
	return int(math.Min(float64(maxInt), math.Max(float64(sign) * float64(quotient), float64(minInt))))
}

总结

移位操作虽然好，但并非唯一解，回忆小时候还没学乘法时，我们也可以用加法模拟乘法，因此利用累加来模拟两数之商更直观。

经过我的尝试，我发现完全减法会导致超时问题，不得不结合移位操作，代码如下所示：

func divide(dividend int, divisor int) int {
	quotient := 0
	maxInt := math.MaxInt32
	minInt := math.MinInt32
	if divisor == 0 || (dividend == minInt && divisor == -1) {
		return maxInt
	}
	// 确定商的符号
	sign := -1
	if (dividend ^ divisor) >= 0 {
		sign = 1
	}

	// 将被除数和除数转换为正数
	positiveDividend, positiveDivisor := int(math.Abs(float64(dividend))), int(math.Abs(float64(divisor)))

	// 每次被除数减去除数的值
	for positiveDividend >= positiveDivisor {
		// 初始化二分搜索的变量
        tempDivisor := positiveDivisor
        multiple := 1
        
        // 执行类似二分搜索的除法
        for positiveDividend >= (tempDivisor << 1) {
            tempDivisor <<= 1
            multiple <<= 1
        }
        
        // 从被除数中减去除数的倍数
        positiveDividend -= tempDivisor
        // 将倍数加到商中
        quotient += multiple
	}
	return int(math.Min(float64(maxInt), math.Max(float64(sign) * float64(quotient), float64(minInt))))
 }