class Solution { public: int divide(int dividend, int divisor) { if ( divisor == 0 ) return INT_MAX; // Handling overflow if( dividend == INT_MIN ) { if( divisor == -1) return INT_MAX; else if( divisor == 1) return INT_MIN; else return ( (divisor & 1 ) == 1 ) ? divide( dividend + 1, divisor) : divide( dividend >> 1, divisor >> 1 ); } if( divisor == INT_MIN ) return 0; int sign = (dividend >= 0) ^ (divisor >= 0) ? -1: 1; long dEnd = abs(dividend); long dSor = abs(divisor); int quotient = 0; while(dEnd >= dSor) { long tmpSor = dSor, q = 1; while( dEnd >= (tmpSor << 1) ) { tmpSor = tmpSor << 1; q = q << 1; } dEnd -= tmpSor; quotient += q; } return sign == 1 ? quotient: -quotient; } };
程式設計可以改變您的未來(Programming can change your future)。 雲林SONG 全名為雲林軟體工程(SOftware eNGineering),目標致力於軟體人才的培養並推廣開源軟體落實於資訊教育。程式設計的觀念是軟體產品的基礎,程式碼就像沙子一樣,要紮實,所建立出來的高塔才會穩固。本站也提供資訊教育相關的教學資源。 YunlinSONG stands for Yunlin SOftware eNGineering, offering tutorial for computer programming and promoting open-source software. Teaching resources in information technology education are provided here.
▼
LeetCode OJ: 29. Divide Two Integers 兩數相除
若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。
題目連結 https://leetcode.com/problems/divide-two-integers/,題目要求不可以用乘法、除法與餘數運算子。從題目分類的Tag上,筆者看到了Binary Search後,就想到位元運算子,只是筆者考慮欠周詳,因為送出後一直得到Wrong Answer阿,原來是忘了考慮Overflow的問題,於是看了此Discuss後,寫了如下的程式碼:
沒有留言:
張貼留言