如何通过移位操作实现两数之商的求法？
摘要：五一漫长的假期，外面的世界是人山人海，反而在家刷题算得上一个好的休闲方式。刚好我开始写这道题： Given two integers `dividend` and&#160
五一漫长的假期，外面的世界是人山人海，反而在家刷题算得上一个好的休闲方式。刚好我开始写这道题：
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` *by* `divisor`.
**Note:** Assume we are dealing with an environment that could only store integers within the**32-bit**signed integer range:`[−231, 231 − 1]`. For this problem, if the quotient is**strictly greater than**`231 - 1`, then return`231 - 1`, and if the quotient is**strictly less than**`-231`, then return`-231`.
**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:**
- `-231 <= dividend, divisor <= 231 - 1`
- `divisor != 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
}
// determine the sign of the quotient
sign := -1
if (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0) {
sign = 1
}
// Convert the dividend and divisor to be positive number
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))))
}
总结
移位操作虽然好，但也不是唯一解，回忆一下小时候还没学乘法的时候，我们也可以用加法去模拟乘法，所以利用累加来模拟出两数之商更直观。
经过我的尝试，我发现完全减法会导致超时问题，不得不结合shifting操作，代码如下所示：
func divide(dividend int, divisor int) int {
quotient := 0
maxInt := math.MaxInt32
minInt := math.MinInt32
if divisor == 0 || (dividend == minInt && divisor == -1) {
return maxInt
}
// determine the sign of the quotient
sign := -1
if (dividend ^ divisor) >= 0 {
sign = 1
}
// Convert the dividend and divisor to be positive number
positiveDividend, positiveDivisor := int(math.Abs(float64(dividend))), int(math.Abs(float64(divisor)))
// Every time postiveDividend subtract with the value of the divisor
for positiveDividend >= positiveDivisor {
// Initialize variables for binary search
tempDivisor := positiveDivisor
multiple := 1
// Perform binary search-like division
for positiveDividend >= (tempDivisor << 1) {
tempDivisor <<= 1
multiple <<= 1
}
// Subtract the multiple of divisor from dividend
positiveDividend -= tempDivisor
// Add the multiple to quotient
quotient += multiple
}
return int(math.Min(float64(maxInt), math.Max(float64(sign) * float64(quotient), float64(minInt))))
}