当前位置：首页 > article >正文

java练习（45）

article 2025/2/28 13:56:51

ps:题目来自力扣

两数相除

给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

返回被除数 dividend 除以除数 divisor 得到的商。

注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−231, 231 − 1] 。本题中，如果商 严格大于 231 − 1 ，则返回 231 − 1 ；如果商 严格小于 -231 ，则返回 -231 。

class Solution {
    public int divide(int dividend, int divisor) {
        // 处理边界情况，当被除数为最小值且除数为 -1 时，结果会超出 32 位有符号整数范围，直接返回最大值
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }

        // 判断结果的符号，通过异或运算判断两数符号是否不同
        boolean negative = (dividend ^ divisor) < 0;

        // 将被除数和除数都转换为负数，因为负数的范围更大，能避免溢出问题
        dividend = -Math.abs(dividend);
        divisor = -Math.abs(divisor);

        int result = 0;
        while (dividend <= divisor) {
            int tempDivisor = divisor;
            int multiple = 1;
            // 不断将除数翻倍，同时倍数也翻倍，直到翻倍后的除数大于当前被除数
            while (dividend - tempDivisor <= tempDivisor) {
                tempDivisor <<= 1;
                multiple <<= 1;
            }
            // 减去当前能减去的最大的除数倍数
            dividend -= tempDivisor;
            // 累加对应的倍数到结果中
            result += multiple;
        }

        // 根据之前判断的符号，决定结果的正负
        return negative ? -result : result;
    }
}

代码解释

本题要求在不使用乘法、除法和取余运算的情况下，计算两个整数的商，并且要考虑 32 位有符号整数的范围。我们可以采用减法和位运算的方法来模拟除法。

具体步骤

处理边界情况：
- 当被除数为 Integer.MIN_VALUE 且除数为 -1 时，商为 Integer.MAX_VALUE + 1，会超出 32 位有符号整数的范围，所以直接返回 Integer.MAX_VALUE。
判断结果的符号：
- 通过异或运算 (dividend ^ divisor) < 0 判断被除数和除数的符号是否不同，如果不同则结果为负。
将被除数和除数转换为负数：
- 为了避免溢出问题，将被除数和除数都转换为负数，因为负数的范围比正数大。
模拟除法过程：
- 使用 while 循环，只要被除数小于等于除数，就继续进行除法操作。
- 在每次循环中：
  - 初始化临时除数 tempDivisor 为除数，倍数 multiple 为 1。
  - 不断将 tempDivisor 翻倍，同时 multiple 也翻倍，直到 tempDivisor 大于当前被除数。
  - 用被除数减去 tempDivisor，并将 multiple 累加到结果 result 中。
根据符号返回结果：
- 根据之前判断的符号，决定最终结果的正负，如果为负则返回 -result，否则返回 result。