LeetCode 29: Divide Two Integers (Bitwise Exponential Subtraction)
LeetCode 29Bit ManipulationMathToday we solve LeetCode 29 - Divide Two Integers.
Source: https://leetcode.com/problems/divide-two-integers/
English
Problem Summary
Given two 32-bit signed integers dividend and divisor, compute the quotient without using multiplication, division, or modulo. Truncate toward zero and clamp overflow to INT_MAX.
Key Insight
Repeatedly subtracting one divisor is too slow. Instead, each round subtract the largest shifted divisor (divisor * 2^k) that still fits, and add 2^k to quotient. This is exponential subtraction.
Brute Force and Limitations
Subtracting |divisor| one by one takes O(|quotient|), which can be up to billions and will time out.
Optimal Algorithm Steps (Bitwise Doubling)
1) Handle overflow special case: INT_MIN / -1 → INT_MAX.
2) Record sign, convert both numbers to positive long values.
3) While remaining dividend is at least divisor, keep left-shifting divisor to find largest chunk.
4) Subtract that chunk and accumulate corresponding power-of-two into quotient.
5) Apply sign and cast back to int.
Complexity Analysis
Time: O(log^2 n) in this nested-shift form (or O(log n) with precomputed shifts).
Space: O(1).
Common Pitfalls
- Forgetting INT_MIN / -1 overflow case.
- Using int during abs conversion (overflow risk).
- Shifting beyond safe range without boundary checks.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int divide(int dividend, int divisor) {
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
boolean negative = (dividend < 0) ^ (divisor < 0);
long a = Math.abs((long) dividend);
long b = Math.abs((long) divisor);
long quotient = 0;
while (a >= b) {
long temp = b;
long multiple = 1;
while ((temp << 1) <= a) {
temp <<= 1;
multiple <<= 1;
}
a -= temp;
quotient += multiple;
}
return negative ? (int) -quotient : (int) quotient;
}
}func divide(dividend int, divisor int) int {
const intMax = 1<<31 - 1
const intMin = -1 << 31
if dividend == intMin && divisor == -1 {
return intMax
}
negative := (dividend < 0) != (divisor < 0)
a := int64(dividend)
if a < 0 {
a = -a
}
b := int64(divisor)
if b < 0 {
b = -b
}
var quotient int64 = 0
for a >= b {
temp := b
multiple := int64(1)
for (temp << 1) <= a {
temp <<= 1
multiple <<= 1
}
a -= temp
quotient += multiple
}
if negative {
return int(-quotient)
}
return int(quotient)
}class Solution {
public:
int divide(int dividend, int divisor) {
if (dividend == INT_MIN && divisor == -1) {
return INT_MAX;
}
bool negative = (dividend < 0) ^ (divisor < 0);
long long a = llabs((long long)dividend);
long long b = llabs((long long)divisor);
long long quotient = 0;
while (a >= b) {
long long temp = b;
long long multiple = 1;
while ((temp << 1) <= a) {
temp <<= 1;
multiple <<= 1;
}
a -= temp;
quotient += multiple;
}
return negative ? (int)-quotient : (int)quotient;
}
};class Solution:
def divide(self, dividend: int, divisor: int) -> int:
INT_MAX = 2**31 - 1
INT_MIN = -2**31
if dividend == INT_MIN and divisor == -1:
return INT_MAX
negative = (dividend < 0) ^ (divisor < 0)
a = abs(dividend)
b = abs(divisor)
quotient = 0
while a >= b:
temp = b
multiple = 1
while (temp << 1) <= a:
temp <<= 1
multiple <<= 1
a -= temp
quotient += multiple
return -quotient if negative else quotientvar divide = function(dividend, divisor) {
const INT_MAX = 2147483647;
const INT_MIN = -2147483648;
if (dividend === INT_MIN && divisor === -1) {
return INT_MAX;
}
const negative = (dividend < 0) !== (divisor < 0);
let a = Math.abs(dividend);
let b = Math.abs(divisor);
let quotient = 0;
while (a >= b) {
let temp = b;
let multiple = 1;
while (temp + temp <= a) {
temp += temp;
multiple += multiple;
}
a -= temp;
quotient += multiple;
}
return negative ? -quotient : quotient;
};中文
题目概述
给定两个 32 位有符号整数 dividend 和 divisor，不使用乘法、除法、取模运算，求商并向零截断。若溢出返回 INT_MAX。
核心思路
不能一下一下减除数，否则太慢。每轮都找“还能减的最大 2 的幂倍除数”，即 divisor * 2^k，然后一次性减掉并把 2^k 加入答案。
基线解法与不足
朴素做法是循环减 |divisor|，复杂度 O(|quotient|)，在大输入下会超时。
最优算法步骤（位运算倍增减法）
1）先处理特殊溢出：INT_MIN / -1。
2）记录符号位，把两数转为正的 long 计算。
3）外层循环保证“被除数剩余值仍 ≥ 除数”。
4）内层不断左移除数，找到当前能减的最大块。
5）减去该块并累加对应倍数，最后恢复符号。
复杂度分析
时间复杂度：此写法为 O(log^2 n)（若预处理位级块可做到 O(log n)）。
空间复杂度：O(1)。
常见陷阱
- 忘记处理 INT_MIN / -1。
- 在 int 上取绝对值导致溢出。
- 左移过程未做边界约束。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int divide(int dividend, int divisor) {
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
boolean negative = (dividend < 0) ^ (divisor < 0);
long a = Math.abs((long) dividend);
long b = Math.abs((long) divisor);
long quotient = 0;
while (a >= b) {
long temp = b;
long multiple = 1;
while ((temp << 1) <= a) {
temp <<= 1;
multiple <<= 1;
}
a -= temp;
quotient += multiple;
}
return negative ? (int) -quotient : (int) quotient;
}
}func divide(dividend int, divisor int) int {
const intMax = 1<<31 - 1
const intMin = -1 << 31
if dividend == intMin && divisor == -1 {
return intMax
}
negative := (dividend < 0) != (divisor < 0)
a := int64(dividend)
if a < 0 {
a = -a
}
b := int64(divisor)
if b < 0 {
b = -b
}
var quotient int64 = 0
for a >= b {
temp := b
multiple := int64(1)
for (temp << 1) <= a {
temp <<= 1
multiple <<= 1
}
a -= temp
quotient += multiple
}
if negative {
return int(-quotient)
}
return int(quotient)
}class Solution {
public:
int divide(int dividend, int divisor) {
if (dividend == INT_MIN && divisor == -1) {
return INT_MAX;
}
bool negative = (dividend < 0) ^ (divisor < 0);
long long a = llabs((long long)dividend);
long long b = llabs((long long)divisor);
long long quotient = 0;
while (a >= b) {
long long temp = b;
long long multiple = 1;
while ((temp << 1) <= a) {
temp <<= 1;
multiple <<= 1;
}
a -= temp;
quotient += multiple;
}
return negative ? (int)-quotient : (int)quotient;
}
};class Solution:
def divide(self, dividend: int, divisor: int) -> int:
INT_MAX = 2**31 - 1
INT_MIN = -2**31
if dividend == INT_MIN and divisor == -1:
return INT_MAX
negative = (dividend < 0) ^ (divisor < 0)
a = abs(dividend)
b = abs(divisor)
quotient = 0
while a >= b:
temp = b
multiple = 1
while (temp << 1) <= a:
temp <<= 1
multiple <<= 1
a -= temp
quotient += multiple
return -quotient if negative else quotientvar divide = function(dividend, divisor) {
const INT_MAX = 2147483647;
const INT_MIN = -2147483648;
if (dividend === INT_MIN && divisor === -1) {
return INT_MAX;
}
const negative = (dividend < 0) !== (divisor < 0);
let a = Math.abs(dividend);
let b = Math.abs(divisor);
let quotient = 0;
while (a >= b) {
let temp = b;
let multiple = 1;
while (temp + temp <= a) {
temp += temp;
multiple += multiple;
}
a -= temp;
quotient += multiple;
}
return negative ? -quotient : quotient;
};
Comments