不使用乘法
*、除法/、取餘%，計算dividend / divisor的整數商（向零取整）。結果須限制在 32 位元有號整數範圍，溢位則回傳2³¹-1。
Example:
Input: dividend = 10, divisor = 3 → 3 Input: dividend = 7, divisor = -3 → -2 Input: dividend = -2147483648, divisor = -1 → 2147483647（溢位夾邊界）
Intuition
TIP
核心思路：用「位元倍增」做減法式除法。每輪盡量把除數左移（×2）到不超過被除數，一次扣掉一大塊，商累加對應的 2 的次方，達到 O(log² n)。
- 純減法
O(n)太慢；倍增讓每輪扣掉最大的divisor × 2^k - 先處理符號，再以絕對值運算；用
Long避免abs(Int.MIN_VALUE)溢位 - 唯一溢位情形：
Int.MIN_VALUE / -1，特判回傳Int.MAX_VALUE
Approaches
1. Brute Force: Repeated Subtraction — O(dividend / divisor) / O(1)
- Idea: 一直把被除數減去除數、計次，直到不夠減
- Time:
O(商的大小)- 最差約 2³¹ 次，會 TLE，僅作對照 - Space:
O(1)
class Solution {
fun divide(dividend: Int, divisor: Int): Int {
if (dividend == Int.MIN_VALUE && divisor == -1) return Int.MAX_VALUE
val negative = (dividend < 0) xor (divisor < 0)
var a = Math.abs(dividend.toLong())
val b = Math.abs(divisor.toLong())
var count = 0L
while (a >= b) { a -= b; count++ }
return (if (negative) -count else count).toInt()
}
}⭐ 2. Bit Doubling (exponential search) — O(log²n) / O(1)
- Idea: 每輪把除數左移到逼近被除數，扣掉後商加上對應的 2 次方
- Time:
O(log² n)- 外層商的位數、內層倍增 - Space:
O(1)
class Solution {
fun divide(dividend: Int, divisor: Int): Int {
// 唯一會溢位的情形
if (dividend == Int.MIN_VALUE && divisor == -1) return Int.MAX_VALUE
val negative = (dividend < 0) xor (divisor < 0)
var a = Math.abs(dividend.toLong()) // 轉 Long 避免 abs(MIN) 溢位
val b = Math.abs(divisor.toLong())
var result = 0L
while (a >= b) {
var temp = b
var multiple = 1L
// 倍增：找最大的 b * 2^k <= a
while (a >= (temp shl 1)) {
temp = temp shl 1
multiple = multiple shl 1
}
a -= temp
result += multiple
}
return (if (negative) -result else result).toInt()
}
}🔑 Takeaways
- Pattern: 位元倍增——用左移取代乘法、減法取代除法
- Key trick:
b shl 1倍增逼近、商累加對應的2^k；先轉Long並特判MIN/-1是避免溢位的兩個關鍵。和 50 Pow(x,n) 的快速冪是同一套「倍增」思維