29. 两数相除

题目描述

输入两个整数：被除数 dividend 和除数 divisor。不准使用乘法、除法和取余运算，算出 dividend 除以 divisor 的商并返回。

商向零取整，即直接丢掉小数部分。例如 8.345 取整为 8，-2.7335 取整为 -2。

假设环境只能存放 32 位有符号整数，范围是 [-2^31, 2^31 - 1]。商大于 2^31 - 1 时返回 2^31 - 1；商小于 -2^31 时返回 -2^31。

示例 1

输入：dividend = 10, divisor = 3
输出：3

解释：10 / 3 = 3.33...，去掉小数得 3。

示例 2

输入：dividend = 7, divisor = -3
输出：-2

解释：7 / -3 = -2.33...，向零取整得 -2。

数据范围

-2^31 <= dividend, divisor <= 2^31 - 1
divisor != 0

解题思路：倍增减法

先处理唯一会溢出的情况 -2^31 / -1，再记下结果符号，对两数取绝对值 a、b。商的二进制可以从高位往低位凑：每一轮把 b 不断翻倍（t += t，相当于左移一位），找到不超过 a 的最大 t = b·2^k，从 a 中减去 t，商加上 2^k。重复直到 a < b。

为什么正确

原被除数 = ans·b + a 始终成立；每轮至少把 a 减半，所以外层循环最多约 32 轮。

复杂度分析

时间 O(log²C)，C 为数值范围（外层、内层各至多约 32 次）；空间 O(1)。

易错点

-2^31 取绝对值会超出 int 范围，C++/Java 要先转成 64 位再取绝对值；-2^31 / -1 = 2^31 必须单独返回 2^31 - 1。翻倍条件写成 a >= t + t，用 64 位就不会溢出。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        INT_MAX, INT_MIN = 2 ** 31 - 1, -2 ** 31
        if dividend == INT_MIN and divisor == -1:
            return INT_MAX
        neg = (dividend < 0) != (divisor < 0)
        a, b = abs(dividend), abs(divisor)
        ans = 0
        while a >= b:
            t, cnt = b, 1
            while a >= t + t:
                t += t
                cnt += cnt
            a -= t
            ans += cnt
        return -ans if neg else ans

class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        boolean neg = (dividend < 0) != (divisor < 0);
        long a = Math.abs((long) dividend), b = Math.abs((long) divisor);
        long ans = 0;
        while (a >= b) {
            long t = b, cnt = 1;
            while (a >= t + t) {
                t += t;
                cnt += cnt;
            }
            a -= t;
            ans += cnt;
        }
        return (int) (neg ? -ans : ans);
    }
}

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) {
            return INT_MAX;
        }
        bool neg = (dividend < 0) != (divisor < 0);
        long long a = llabs((long long)dividend), b = llabs((long long)divisor);
        long long ans = 0;
        while (a >= b) {
            long long t = b, cnt = 1;
            while (a >= t + t) {
                t += t;
                cnt += cnt;
            }
            a -= t;
            ans += cnt;
        }
        return (int)(neg ? -ans : ans);
    }
};

func divide(dividend int, divisor int) int {
	INT_MAX, INT_MIN := 1<<31-1, -(1 << 31)
	if dividend == INT_MIN && divisor == -1 {
		return INT_MAX
	}
	neg := (dividend < 0) != (divisor < 0)
	a, b := dividend, divisor
	if a < 0 {
		a = -a
	}
	if b < 0 {
		b = -b
	}
	ans := 0
	for a >= b {
		t, cnt := b, 1
		for a >= t+t {
			t += t
			cnt += cnt
		}
		a -= t
		ans += cnt
	}
	if neg {
		return -ans
	}
	return ans
}

var divide = function(dividend, divisor) {
    const INT_MAX = 2 ** 31 - 1, INT_MIN = -(2 ** 31);
    if (dividend === INT_MIN && divisor === -1) {
        return INT_MAX;
    }
    const neg = (dividend < 0) !== (divisor < 0);
    let a = Math.abs(dividend), b = Math.abs(divisor);
    let ans = 0;
    while (a >= b) {
        let t = b, cnt = 1;
        while (a >= t + t) {
            t += t;
            cnt += cnt;
        }
        a -= t;
        ans += cnt;
    }
    return neg ? 0 - ans : ans;
};

function divide(dividend: number, divisor: number): number {
    const INT_MAX = 2 ** 31 - 1, INT_MIN = -(2 ** 31);
    if (dividend === INT_MIN && divisor === -1) {
        return INT_MAX;
    }
    const neg = (dividend < 0) !== (divisor < 0);
    let a = Math.abs(dividend), b = Math.abs(divisor);
    let ans = 0;
    while (a >= b) {
        let t = b, cnt = 1;
        while (a >= t + t) {
            t += t;
            cnt += cnt;
        }
        a -= t;
        ans += cnt;
    }
    return neg ? 0 - ans : ans;
}

载入编辑器，自己跑一遍 →

其他解法

倍增减法和二分 + 快速乘都是 O(log² C)；类二进制拆分预先存好倍数表，从高位贪心一遍得到商，只需 O(log C)。

解法 2：类二进制拆分时间 O(log C)，空间 O(log C)

取绝对值后，先用自加得到 b、2b、4b……直到超过 a，并同步记录对应的倍数 1、2、4……。再从最大的倍数往小试：当前余数 a 不小于 2^i·b 时就减去它，并把 2^i 加进商。这相当于从高位到低位逐位确定商的二进制表示。C 是被除数的绝对值。

倍数表只算一次，每一位只试一次，时间从 O(log² C) 降到 O(log C)。需要额外保存至多 32 个倍数。

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        INT_MAX, INT_MIN = 2 ** 31 - 1, -2 ** 31
        if dividend == INT_MIN and divisor == -1:
            return INT_MAX
        neg = (dividend < 0) != (divisor < 0)
        a, b = abs(dividend), abs(divisor)
        dbl, cnt = [b], [1]
        while dbl[-1] + dbl[-1] <= a:
            dbl.append(dbl[-1] + dbl[-1])
            cnt.append(cnt[-1] + cnt[-1])
        ans = 0
        for i in range(len(dbl) - 1, -1, -1):
            if a >= dbl[i]:
                a -= dbl[i]
                ans += cnt[i]
        return -ans if neg else ans

class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        boolean neg = (dividend < 0) != (divisor < 0);
        long a = Math.abs((long) dividend), b = Math.abs((long) divisor);
        List<Long> dbl = new ArrayList<>(), cnt = new ArrayList<>();
        dbl.add(b); cnt.add(1L);
        while (dbl.get(dbl.size() - 1) + dbl.get(dbl.size() - 1) <= a) {
            long d = dbl.get(dbl.size() - 1), c = cnt.get(cnt.size() - 1);
            dbl.add(d + d);
            cnt.add(c + c);
        }
        long ans = 0;
        for (int i = dbl.size() - 1; i >= 0; i--) {
            if (a >= dbl.get(i)) {
                a -= dbl.get(i);
                ans += cnt.get(i);
            }
        }
        return (int) (neg ? -ans : ans);
    }
}

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) return INT_MAX;
        bool neg = (dividend < 0) != (divisor < 0);
        long long a = llabs((long long)dividend), b = llabs((long long)divisor);
        vector<long long> dbl{b}, cnt{1};
        while (dbl.back() + dbl.back() <= a) {
            dbl.push_back(dbl.back() + dbl.back());
            cnt.push_back(cnt.back() + cnt.back());
        }
        long long ans = 0;
        for (int i = (int)dbl.size() - 1; i >= 0; i--) {
            if (a >= dbl[i]) {
                a -= dbl[i];
                ans += cnt[i];
            }
        }
        return (int)(neg ? -ans : ans);
    }
};

func divide(dividend int, divisor int) int {
	INT_MAX, INT_MIN := 1<<31-1, -(1 << 31)
	if dividend == INT_MIN && divisor == -1 {
		return INT_MAX
	}
	neg := (dividend < 0) != (divisor < 0)
	a, b := dividend, divisor
	if a < 0 {
		a = -a
	}
	if b < 0 {
		b = -b
	}
	dbl, cnt := []int{b}, []int{1}
	for dbl[len(dbl)-1]+dbl[len(dbl)-1] <= a {
		dbl = append(dbl, dbl[len(dbl)-1]+dbl[len(dbl)-1])
		cnt = append(cnt, cnt[len(cnt)-1]+cnt[len(cnt)-1])
	}
	ans := 0
	for i := len(dbl) - 1; i >= 0; i-- {
		if a >= dbl[i] {
			a -= dbl[i]
			ans += cnt[i]
		}
	}
	if neg {
		return -ans
	}
	return ans
}

var divide = function(dividend, divisor) {
    const INT_MAX = 2 ** 31 - 1, INT_MIN = -(2 ** 31);
    if (dividend === INT_MIN && divisor === -1) return INT_MAX;
    const neg = (dividend < 0) !== (divisor < 0);
    let a = Math.abs(dividend);
    const b = Math.abs(divisor);
    const dbl = [b], cnt = [1];
    while (dbl[dbl.length - 1] + dbl[dbl.length - 1] <= a) {
        dbl.push(dbl[dbl.length - 1] + dbl[dbl.length - 1]);
        cnt.push(cnt[cnt.length - 1] + cnt[cnt.length - 1]);
    }
    let ans = 0;
    for (let i = dbl.length - 1; i >= 0; i--) {
        if (a >= dbl[i]) {
            a -= dbl[i];
            ans += cnt[i];
        }
    }
    return neg ? 0 - ans : ans;
};

function divide(dividend: number, divisor: number): number {
    const INT_MAX = 2 ** 31 - 1, INT_MIN = -(2 ** 31);
    if (dividend === INT_MIN && divisor === -1) return INT_MAX;
    const neg = (dividend < 0) !== (divisor < 0);
    let a = Math.abs(dividend);
    const b = Math.abs(divisor);
    const dbl: number[] = [b], cnt: number[] = [1];
    while (dbl[dbl.length - 1] + dbl[dbl.length - 1] <= a) {
        dbl.push(dbl[dbl.length - 1] + dbl[dbl.length - 1]);
        cnt.push(cnt[cnt.length - 1] + cnt[cnt.length - 1]);
    }
    let ans = 0;
    for (let i = dbl.length - 1; i >= 0; i--) {
        if (a >= dbl[i]) {
            a -= dbl[i];
            ans += cnt[i];
        }
    }
    return neg ? 0 - ans : ans;
}

解法 3：二分查找 + 快速乘时间 O(log² C)，空间 O(1)

商 q 满足单调性：q·b ≤ a 对小的 q 成立，对大的 q 不成立。在 [0, a] 上二分查找最大的满足条件的 q。判断 q·b ≤ a 时不用乘法，而是按 q 的二进制位累加倍增的 b（快速乘），累加和一旦超过 a 就提前返回。

把除法转化为「二分答案 + 判定」，模板通用。每次判定要 O(log C)，总时间不如类二进制拆分。

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        INT_MAX, INT_MIN = 2 ** 31 - 1, -2 ** 31
        if dividend == INT_MIN and divisor == -1:
            return INT_MAX
        neg = (dividend < 0) != (divisor < 0)
        a, b = abs(dividend), abs(divisor)

        def fits(q):
            res, add = 0, b
            while q:
                if q & 1:
                    res += add
                    if res > a:
                        return False
                q >>= 1
                if q:
                    add += add
            return True

        lo, hi = 0, a
        while lo < hi:
            mid = lo + ((hi - lo + 1) >> 1)
            if fits(mid):
                lo = mid
            else:
                hi = mid - 1
        return -lo if neg else lo

class Solution {
    long a, b;

    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        boolean neg = (dividend < 0) != (divisor < 0);
        a = Math.abs((long) dividend); b = Math.abs((long) divisor);
        long lo = 0, hi = a;
        while (lo < hi) {
            long mid = lo + ((hi - lo + 1) >> 1);
            if (fits(mid)) lo = mid;
            else hi = mid - 1;
        }
        return (int) (neg ? -lo : lo);
    }

    boolean fits(long q) {
        long res = 0, add = b;
        while (q > 0) {
            if ((q & 1) == 1) {
                res += add;
                if (res > a) return false;
            }
            q >>= 1;
            if (q > 0) add += add;
        }
        return true;
    }
}

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) return INT_MAX;
        bool neg = (dividend < 0) != (divisor < 0);
        long long a = llabs((long long)dividend), b = llabs((long long)divisor);
        auto fits = [&](long long q) {
            long long res = 0, add = b;
            while (q) {
                if (q & 1) {
                    res += add;
                    if (res > a) return false;
                }
                q >>= 1;
                if (q) add += add;
            }
            return true;
        };
        long long lo = 0, hi = a;
        while (lo < hi) {
            long long mid = lo + ((hi - lo + 1) >> 1);
            if (fits(mid)) lo = mid;
            else hi = mid - 1;
        }
        return (int)(neg ? -lo : lo);
    }
};

func divide(dividend int, divisor int) int {
	INT_MAX, INT_MIN := 1<<31-1, -(1 << 31)
	if dividend == INT_MIN && divisor == -1 {
		return INT_MAX
	}
	neg := (dividend < 0) != (divisor < 0)
	a, b := dividend, divisor
	if a < 0 {
		a = -a
	}
	if b < 0 {
		b = -b
	}
	fits := func(q int) bool {
		res, add := 0, b
		for q > 0 {
			if q&1 == 1 {
				res += add
				if res > a {
					return false
				}
			}
			q >>= 1
			if q > 0 {
				add += add
			}
		}
		return true
	}
	lo, hi := 0, a
	for lo < hi {
		mid := lo + (hi-lo+1)>>1
		if fits(mid) {
			lo = mid
		} else {
			hi = mid - 1
		}
	}
	if neg {
		return -lo
	}
	return lo
}

var divide = function(dividend, divisor) {
    const INT_MAX = 2 ** 31 - 1, INT_MIN = -(2 ** 31);
    if (dividend === INT_MIN && divisor === -1) return INT_MAX;
    const neg = (dividend < 0) !== (divisor < 0);
    const a = Math.abs(dividend), b = Math.abs(divisor);
    const fits = (q) => {
        let res = 0, add = b;
        while (q > 0) {
            if (q & 1) {
                res += add;
                if (res > a) return false;
            }
            q = q >>> 1;
            if (q > 0) add += add;
        }
        return true;
    };
    let lo = 0, hi = a;
    while (lo < hi) {
        const mid = lo + ((hi - lo + 1) >>> 1);
        if (fits(mid)) lo = mid;
        else hi = mid - 1;
    }
    return neg ? 0 - lo : lo;
};

function divide(dividend: number, divisor: number): number {
    const INT_MAX = 2 ** 31 - 1, INT_MIN = -(2 ** 31);
    if (dividend === INT_MIN && divisor === -1) return INT_MAX;
    const neg = (dividend < 0) !== (divisor < 0);
    const a = Math.abs(dividend), b = Math.abs(divisor);
    const fits = (q: number): boolean => {
        let res = 0, add = b;
        while (q > 0) {
            if (q & 1) {
                res += add;
                if (res > a) return false;
            }
            q = q >>> 1;
            if (q > 0) add += add;
        }
        return true;
    };
    let lo = 0, hi = a;
    while (lo < hi) {
        const mid = lo + ((hi - lo + 1) >>> 1);
        if (fits(mid)) lo = mid;
        else hi = mid - 1;
    }
    return neg ? 0 - lo : lo;
}

位运算专题的其他题目

查看位运算全部题目 →