Medium

题目描述

给定两个整数 dividend 和 divisor，在不使用乘法、除法和取模运算符的情况下，将两个整数相除。

整数除法应该向零截断，这意味着失去小数部分。例如，8.345 会被截断为 8，而 -2.7335 会被截断为 -2。

返回 dividend 除以 divisor 后的商。

**注意：**假设我们处于一个只能存储 32 位有符号整数范围内的整数的环境：[−2³¹, 2³¹ − 1]。对于这个问题，如果商严格大于 2³¹ − 1，则返回 2³¹ − 1，如果商严格小于 −2³¹，则返回 −2³¹。

示例 1：

输入：dividend = 10, divisor = 3
输出：3
解释：10/3 = 3.33333.. 被截断为 3。

示例 2：

输入：dividend = 7, divisor = -3
输出：-2
解释：7/-3 = -2.33333.. 被截断为 -2。

提示：

  • -2³¹ <= dividend, divisor <= 2³¹ - 1
  • divisor != 0

解题思路

这道题的核心是在不使用乘法、除法和取模运算的情况下实现除法操作。

基本思路： 使用位运算来模拟除法过程。除法的本质是计算被除数包含多少个除数。我们可以通过左移操作（相当于乘以2的幂）来快速逼近结果。

算法步骤：

  1. 处理边界情况：检查溢出情况，特别是 INT_MIN / -1 会溢出
  2. 确定结果符号：根据被除数和除数的符号确定最终结果的符号
  3. 转换为正数：将两个数都转换为正数进行计算，但要注意 INT_MIN 的绝对值会溢出，所以统一转换为负数处理更安全
  4. 位运算逼近：使用左移操作让除数逐步逼近被除数，每次尝试减去 divisor * 2^k 的最大可能值
  5. 累计商：将每次成功减去的倍数累加到结果中

优化要点：

  • 使用负数进行计算避免溢出问题
  • 通过位运算实现快速倍增，时间复杂度从 O(n) 降低到 O(log n)
  • 仔细处理边界情况和符号

代码实现

class Solution {
public:
    int divide(int dividend, int divisor) {
        // 处理溢出情况
        if (dividend == INT_MIN && divisor == -1) {
            return INT_MAX;
        }
        
        // 确定结果符号
        bool negative = (dividend < 0) ^ (divisor < 0);
        
        // 转换为负数进行计算（避免溢出）
        if (dividend > 0) dividend = -dividend;
        if (divisor > 0) divisor = -divisor;
        
        int result = 0;
        while (dividend <= divisor) {
            int temp = divisor;
            int count = 1;
            
            // 找到最大的 temp 使得 dividend <= temp
            while (dividend <= (temp << 1) && (temp << 1) < 0) {
                temp <<= 1;
                count <<= 1;
            }
            
            dividend -= temp;
            result += count;
        }
        
        return negative ? -result : result;
    }
};

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # 处理溢出情况
        if dividend == -2**31 and divisor == -1:
            return 2**31 - 1
        
        # 确定结果符号
        negative = (dividend < 0) ^ (divisor < 0)
        
        # 转换为负数进行计算（避免溢出）
        if dividend > 0:
            dividend = -dividend
        if divisor > 0:
            divisor = -divisor
        
        result = 0
        while dividend <= divisor:
            temp = divisor
            count = 1
            
            # 找到最大的 temp 使得 dividend <= temp
            while dividend <= (temp << 1) and (temp << 1) < 0:
                temp <<= 1
                count <<= 1
            
            dividend -= temp
            result += count
        
        return -result if negative else result

public class Solution {
    public int Divide(int dividend, int divisor) {
        // 处理溢出情况
        if (dividend == int.MinValue && divisor == -1) {
            return int.MaxValue;
        }
        
        // 确定结果符号
        bool negative = (dividend < 0) ^ (divisor < 0);
        
        // 转换为负数进行计算（避免溢出）
        if (dividend > 0) dividend = -dividend;
        if (divisor > 0) divisor = -divisor;
        
        int result = 0;
        while (dividend <= divisor) {
            int temp = divisor;
            int count = 1;
            
            // 找到最大的 temp 使得 dividend <= temp
            while (dividend <= (temp << 1) && (temp << 1) < 0) {
                temp <<= 1;
                count <<= 1;
            }
            
            dividend -= temp;
            result += count;
        }
        
        return negative ? -result : result;
    }
}

var divide = function(dividend, divisor) {
    const MAX_INT = 2147483647;
    const MIN_INT = -2147483648;
    
    if (dividend === MIN_INT && divisor === -1) {
        return MAX_INT;
    }
    
    const negative = (dividend < 0) !== (divisor < 0);
    
    let absDividend = Math.abs(dividend);
    let absDivisor = Math.abs(divisor);
    
    let result = 0;
    
    while (absDividend >= absDivisor) {
        let temp = absDivisor;
        let multiple = 1;
        
        while (absDividend >= (temp << 1)) {
            temp <<= 1;
            multiple <<= 1;
        }
        
        absDividend -= temp;
        result += multiple;
    }
    
    result = negative ? -result : result;
    
    return Math.max(MIN_INT, Math.min(MAX_INT, result));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log²n)外层循环最多执行 log n 次，内层循环也最多执行 log n 次
空间复杂度O(1)只使用常数个额外变量