[LeetCode] Divide two integers

這題之前實驗室同學面試前有刷過,前陣子聚餐好像有聽到她在說這題

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的方式