難度: Medium
類型: Math, Bit Manipulation
CPP程式下載: 29.cpp
前情題要:
兩個整數的除法, 但不能用到乘法與餘數(Mod)的運算。
思考方式:
如果知道方法的話, 這一題很簡單, 只要小心處理正負與極值就好。
1. 先判斷除數和被除數的正負, 之後就知道商的正負號。後面就都用正整數做除法。
2. 把十進位的除法改為二進位的除法就好。先把除數一直乘二直到最大但不大過被除數。然後兩個數字相減, 得到餘數。餘數再和除數退一位(bit)再比較, 大於就相減,然後商多1。最後的商也是二進位。就轉成10進位就可以了。
3. 處理商的極值若超過2^31, 就改為2^31 (正負都是)。
複雜度思考:
Time Complexity: O( 2*31 ) (最多)
Space Complexity: O( x )
結果:
Runtime: 0 ms, Beats: 100%
Memory: 8.48 MB, Beats: 96.80%
