LeetCode 29 兩數相除 - 不用乘除取模實現整數除法

題目翻譯

給定兩個整數 dividend（被除數）和 divisor（除數），在 不使用乘法、除法、取模運算 的情況下計算商。若結果溢出 32 位有符號整數範圍，返回 INT_MAX (2,147,483,647)。

核心思路：位運算模擬長除法

利用二進制特性：任何整數可表示為 2 的冪次之和。我們嘗試用除數的倍數（通過左移實現乘 2）去減被除數，從最高位（第 31 位）開始試減，每成功減一次，就在商的對應位置上標記 1。這相當於在做「二進制長除法」。

關鍵細節

• 處理符號：先記錄正負號，將兩數轉為 unsigned int 或 long long 進行運算，避免 INT_MIN 取絕對值溢出。
• 溢出邊界：divisor == 0 或 dividend == INT_MIN && divisor == -1 直接返回 INT_MAX。
• 位移試減：對於 32 位整數，從 i = 31 遞減到 0，維護一個餘數 rem，每輪左移 1 位並帶入被除數的當前位；若 rem >= divisor，則減去除數，並在商的第 i 位置 1。

參考實現 (C++)

class Solution {
public:
    int divide(int dividend, int divisor) {
        // 溢出與特殊情況
        if (divisor == 0) return INT_MAX;
        if (divisor == 1) return dividend;
        if (divisor == -1) {
            if (dividend == INT_MIN) return INT_MAX;
            return -dividend;
        }

        bool neg = (dividend < 0) ^ (divisor < 0);
        unsigned int a = dividend < 0 ? - (unsigned int)dividend : dividend;
        unsigned int b = divisor  < 0 ? - (unsigned int)divisor  : divisor;

        unsigned int quotient = 0, remainder = 0;
        for (int i = 31; i >= 0; --i) {
            remainder = (remainder << 1) | ((a >> i) & 1);
            if (remainder >= b) {
                remainder -= b;
                quotient |= (1u << i);
            }
        }
        return neg ? - (int)quotient : (int)quotient;
    }
};

另一種寫法：倍增減法 (Java)

public int divide(int dividend, int divisor) {
    if (divisor == 0 || (dividend == Integer.MIN_VALUE && divisor == -1))
        return Integer.MAX_VALUE;
    int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;
    long a = Math.abs((long)dividend), b = Math.abs((long)divisor), res = 0;
    while (a >= b) {
        long tb = b, cnt = 1;
        while (a >= (tb << 1)) { tb <<= 1; cnt <<= 1; }
        a -= tb;
        res += cnt;
    }
    return (int)(sign * res);
}

總結

本題考察位運算與邊界處理。關鍵在於將除法轉化為「被除數 = 商 × 除數 + 餘數」的二進制構建過程，利用左移快速構建除數的倍數，時間複雜度 O(32) = O(1)。