剑指 Offer II 001 整数除法
2022-07-28
2分钟阅读时长
剑指 Offer II 001 整数除法
给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。
注意：
- 整数除法的结果应当截去（
truncate）其小数部分，例如：truncate(8.345) = 8以及truncate(-2.7335) = -2 - 假设我们的环境只能存储 32 位有符号整数，其数值范围是
[−231, 231−1]。本题中，如果除法结果溢出，则返回231 − 1
示例 1：
输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7
示例 2：
输入：a = 7, b = -3 输出：-2 解释：7/-3 = truncate(-2.33333..) = -2
示例 3：
输入：a = 0, b = 1
输出：0示例 4：
输入：a = 1, b = 1
输出：1
提示:
-231 <= a, b <= 231 - 1b != 0
注意：本题与主站 29 题相同：https://leetcode-cn.com/problems/divide-two-integers/
书中解法，LC 执行超时
func divide(dividend int, divisor int) int {
// math.MinInt32 => 0x80000000
// 边界处理
if dividend == math.MinInt32 && divisor == -1 {
return math.MaxInt32
}
// 防止溢出，转为负数再处理
negative := 2
if dividend > 0 {
negative--
dividend = -dividend
}
if divisor > 0 {
negative--
divisor = -divisor
}
result := divideCore(dividend, divisor)
// 除数和被除数符号位不同
if negative == 1 {
return -result
} else {
return result
}
}
func divideCore(dividend int, divisor int) int {
// math.MinInt32 >> 1 相当于 0xc0000000
result, middle := 0, math.MinInt32 >> 1
for dividend <= divisor {
value := divisor
quotient := 1
for value >= middle && dividend <= value + value {
quotient += quotient
value += value
}
result += quotient
dividend -= value
}
return result
}
LC官方二分法
位运算
// 时间复杂度：O(1)
func divide(a int, b int) int {
if a == math.MinInt32 && b == -1 {
return math.MaxInt32
}
// 处理边界，防止转正数溢出, 除数绝对值最大，结果必为 0 或 1
if b == math.MinInt32 {
if a == b {
return 1
} else {
return 0
}
}
ans := 0
// 被除数先减去一个除数
if (a == math.MinInt32) {
a -= -abs(b);
ans += 1;
}
sign := 1
if (a > 0 && b < 0) || (a < 0 && b > 0) {
sign = -1
}
a, b = abs(a), abs(b)
for i := 31; i >= 0; i-- {
if (a >> i) - b >= 0 {
a = a - (b << i)
// 代码优化：这里控制 ans 大于等于 INT_MAX
if ans > math.MaxInt32 - (1 << i) {
return math.MinInt32
}
ans += 1 << i
}
}
return sign * res
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}