LeetCode 29. 两数相除 - Rust 实现核心思路这道题要求不使用乘法、除法和取模运算符来实现整数除法。标准解法是倍增法位移模拟处理符号记录结果的符号将两个数转为同号处理倍增逼近将除数不断左移×2找到不超过被除数的最大值累加商值对应左移的位数累加1 n到结果处理余数用被除数减去已逼近的值重复上述过程溢出处理-2^31 / -1结果超出i32范围需返回i32::MAXimplSolution{pubfndivide(dividend:i32,divisor:i32)-i32{// 处理溢出唯一情况-2^31 / -1 2^31超出 i32 范围ifdividendi32::MINdivisor-1{returni32::MAX;}// 判断结果符号异号为负letnegative(dividend0)!(divisor0);// 转为 i64 并取绝对值避免溢出i32::MIN 的绝对值会溢出letmutdvd(dividendasi64).abs();letmutdvs(divisorasi64).abs();letmutresult:i640;whiledvddvs{letmuttempdvs;letmutmultiple1_i64;// 倍增除数不断左移×2直到超过被除数// temp 1 等价于 temp * 2但使用位移更直观whiledvd(temp1){temp1;multiple1;}// 减去已逼近的值累加对应商dvd-temp;resultmultiple;}// 根据符号返回结果ifnegative{-(resultasi32)}else{resultasi32}}}复杂度分析指标 复杂度 说明时间 O(log²N) 外层循环 O(log N) 次内层倍增 O(log N) 次空间 O(1) 仅使用常数个变量关键点说明为什么用i64i32::MIN的绝对值是2^31超出i32::MAX (2^31-1)会溢出。转为i64后安全处理。为什么temp 1不会溢出循环条件dvd (temp 1)保证了temp始终不超过dvd而dvd最大为|i32::MIN| 2^31在i64范围内完全安全。位移与乘法的关系temp 1等价于temp * 2multiple 1等价于multiple * 2。题目禁止乘法但允许位移位运算这是标准解法。符号处理技巧(dividend 0) ! (divisor 0)比分别判断四种情况更简洁两数符号不同则为true结果为负。