LeetCode LCR 001. 两数相除

Categories:

题目描述
思路分析
1. 解法一：位运算加速减法（推荐）
相似题目

题目描述

✅ LCR 001. 两数相除

思路分析

解法一：位运算加速减法（推荐）

核心思路：

除法等价于不断减去除数，使用倍增（指数级）减少次数。

用 divisor << k 寻找不超过被除数的最大倍数。

注意溢出与符号处理。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示被除数绝对值。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }

        long a = Math.abs((long) dividend);
        long b = Math.abs((long) divisor);
        long res = 0;

        // 倍增寻找最大可减倍数
        while (a >= b) {
            long temp = b;
            long multiple = 1;

            while (a >= (temp << 1)) {
                temp <<= 1;
                multiple <<= 1;
            }

            a -= temp;
            res += multiple;
        }

        boolean sameSign = (dividend ^ divisor) >= 0;
        return sameSign ? (int) res : (int) -res;
    }
}

func divide(dividend int, divisor int) int {
	if dividend == -1<<31 && divisor == -1 {
		return 1<<31 - 1
	}

	a := int64(dividend)
	b := int64(divisor)
	if a < 0 {
		a = -a
	}
	if b < 0 {
		b = -b
	}

	var res int64

	// 倍增寻找最大可减倍数
	for a >= b {
		temp := b
		multiple := int64(1)

		for a >= (temp << 1) {
			temp <<= 1
			multiple <<= 1
		}

		a -= temp
		res += multiple
	}

	sameSign := (dividend^divisor) >= 0
	if sameSign {
		return int(res)
	}
	return int(-res)
}

相似题目

题目	难度	考察点
50. Pow(x, n)	中等	快速幂
69. x 的平方根	简单	二分
7. 整数反转	中等	溢出处理
43. 字符串相乘	中等	大数运算
8. 字符串转换整数 (atoi)	中等	边界处理

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/80034294