這題之前實驗室同學面試前有刷過,前陣子聚餐好像有聽到她在說這題
https://leetcode.com/problems/divide-two-integers/description/
不能用 * / % 這幾個operator
所以能用的其實就滿少的,跟加減乘除有關係的大概就只剩加減號XDD
但總不可能用慢慢減的,所以想這應該是跟 shift有關係的 <<
乍看之下<<這個operator好像只跟2有關係
不過後來想想任何數字都能用bits 2的冪次做表示啊,代表商數也可以
舉個例子 86除以3 可以看成 86=3*24+2
24這個商數可以看成 16+8=2^4+2^3
然後86可以看成 = 3(2^4+2^3)+2
所以第一步驟就是找到組成商數裡的那個最大2冪次
然後 86-24*3 = 14 再繼續重複剛剛的步驟
一直拆解到最後不能再除為止
上述所說的就是loop裡面在做的事
其餘是一些邊界case的判斷、解overflow的方式
class Solution { public: int divide(int dividend, int divisor) { if (!divisor || (dividend == INT_MIN && divisor == -1)) return INT_MAX; int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1; int ans = 0; long long divid = labs(dividend); long long divis = labs(divisor); while(divid >= divis) { long long tmp = divis; long long tmp_multiple = 1; while(divid >= tmp) { tmp = tmp << 1; tmp_multiple = tmp_multiple << 1; } divid -= tmp >> 1; ans += tmp_multiple >> 1; } return sign == 1 ? ans : -ans; } };