Leetcode (Python): Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

Solution:

The result can be seen as $a_n 2^n+ a_{n-1} 2^{n-1}+\dots+a_1 *2 +a_0$, with $a_i \in \{0,1\}$. Our solution calculates first n by obtaining the largest n that $\text{divisor} \cdot 2^n \leq \text{dividend}$. Then we just have to calculate $a_i = \left( \text{dividend} - \sum_{j=i+1}^n a_j \text{divisor} \cdot 2^j\right)>= 2^i$, even the expression is complex the code is much simpler:

class Solution:
    # @return an integer
    def divide(self, dividend, divisor):
        isNegative = (dividend<0) ^ (divisor<0)
        dividend = abs(dividend)
        divisor = abs(divisor)
        count = 1
        while dividend >= (divisor<<1):
            divisor <<= 1
            count <<=1
        result = 0
        while dividend > 0 and divisor>=1:
            if dividend>=divisor:
                dividend -= divisor
                result += count
            divisor >>= 1
            count >>=1
        if isNegative:
            return -result
        else:
            return result