LeetCode 29. 两数相除 — C 语言实现核心思路倍增法位移模拟#includelimits.hintdivide(intdividend,intdivisor){// 唯一溢出情况-2^31 / -1 2^31超出 32 位有符号整数范围if(dividendINT_MINdivisor-1){returnINT_MAX;}// 判断结果符号两数符号不同则为负intnegative(dividend0)!(divisor0);// 转为 long long 并取绝对值// C 中 abs(INT_MIN) 会溢出必须用 64 位整数longlongdvddividend;longlongdvsdivisor;if(dvd0)dvd-dvd;if(dvs0)dvs-dvs;longlongresult0;while(dvddvs){longlongtempdvs;longlongmultiple1;// 内层循环除数不断左移翻倍×2直到超过被除数// temp 1 等价于 temp * 2符合不用乘法的要求while(dvd(temp1)){temp1;multiple1;}// 减去已逼近的值累加对应商dvd-temp;resultmultiple;}// 还原符号if(negative){result-result;}// 截断到 32 位有符号整数范围if(resultINT_MAX)returnINT_MAX;if(resultINT_MIN)returnINT_MIN;return(int)result;}执行流程图解以divide(10, 3)为例轮次 dvd剩余 temp当前除数倍数 multiple当前商倍数 result累计商初始 10 — — 0第1轮 10 → 1 3 → 6 → 12停→ 回退到 6 1 → 2 → 4停→ 回退到 2 0 2 2第2轮 1 3 1内层不执行 1 2 0 2循环结束最终result 3余数dvd 1。复杂度分析指标 复杂度 说明时间 O(log²N) 外层循环 O(log N)内层倍增 O(log N)空间 O(1) 仅使用常数变量C 语言特有关键点为什么必须用long longC 标准库abs(INT_MIN)的行为是未定义UB因为|−2^31| 2^31超出了int正数范围。必须先用long long承接再取相反数。符号判断技巧(dividend 0) ! (divisor 0)比写四个if分支更简洁两数符号不同则为1结果为负。位移与乘法temp 1等价于temp * 2multiple 1等价于multiple * 2。题目禁止*运算符但位运算是允许的。最后的截断虽然本题只有INT_MIN / -1一种溢出情况已在开头处理但末尾保留截断逻辑可防御其他边界问题使代码更健壮。