## [29\. 兩數相除](https://leetcode-cn.com/problems/divide-two-integers/) > Medium #### 思路 剛看題目第一反應直接使用python3中`//`求商并向下去整操作，商為負數情況需處理一下，但是題目要求不能使用除法運算符。過！ <br> 沒有想法，學習一波大佬解法，獲得新思路 * `A / B = C` => `找到一個整數T，使得B的T倍最接近A但是不超過A` * 負數轉成正數統一考慮，最后將負數符號添加 * 不能使用乘法操作，倍數操作使用`位運算` * n >> m => `$ n/2^{m} $` * n << m => `$ n * 2^{m} $` * 倍數增長次數太多 => TLE * 指數增長，超出之后再遞歸復位到1指數增長，優化增長速度 解題過程需考慮邊界條件（`$ [-2^{31}, 2^{31} - 1] $`），以及除數為0的情況 <br> #### 代碼 python3 ``` class?Solution: def?divide(self,?dividend:?int,?divisor:?int)?->?int: if?divisor?==?0: return0 if?dividend?==?(0?-?(2?<<?30))?and?divisor?==?\-1: return?(2?<<?30)?-?1 if?(dividend?>?0and?divisor?>?0)?or?(dividend?<?0and?divisor?<?0): ???????? tag?=?1 else: ????????????tag?=?-1 ????????dividend?=?abs(dividend) ????????divisor?=?abs(divisor) ????????res?=?dividend ????????c?=?0 while?res?>=?divisor: ????????????a?=?0 while?res?-?(divisor?=?0: ????????????????res?=?res?-?(divisor?<<?a) ????????????????a?+=?1 if?a?>=?0: ????????????????c?+=?(2?<<?a?-?1)?-?1 return?c?if?tag?==?1else0?-?c ```