不用乘除实现两数相除(LC29)
哪些公司问过
答案要点
- 朴素做法:反复减除数,最坏O(n)
- 位移倍增:从高位到低位确定商的每一位
- 除数左移i位不超过余数时,减去并在商上加1<<i
- 复杂度O(log n),本质是二进制竖式除法
- 处理除数为0、INT_MIN/-1溢出和符号,结果向零截断
易错点
- INT_MIN取绝对值溢出
- 忽略INT_MIN除以-1的溢出
- 除数左移时越界变成负数,导致判断错误
面试官常见追问
- 不能用64位整数时怎么处理溢出?
- 如何用加法和位运算实现乘法?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。