# Clean solution with Bit Manipulation

• A non-negative integer can be represented as `a0*2^0 + a1*2^1 + a2*2^2 + ... + an*2^n`, so given `x`, we can calculate `a0, a1, a2, ..., an` as:

``````def getA(x):
bit = 1
while bit < x:
bit <<= 1

A = []
while bit:
a = bit <= x
A.append(a)

x -= a * bit
bit >>= 1

return A
``````

If `dividend = div * divisor + mod`, and `div` can be represented as `a0*2^0 + a1*2^1 + a2*2^2 + ... + an*2^n`, then `dividend = (a0*2^0 + a1*2^1 + a2*2^2 + ... + an*2^n) * divisor + mod`. So we just need to calculate `a0, a1, a2, ... an`, and we will get `div`.

According above, we have below solution, be aware of overflow situations.

``````class Solution(object):
def divide(self, dividend, divisor):
MAX_INT, MIN_INT = 2 ** 31 - 1, -2 ** 31

if divisor == 0 or dividend == MIN_INT and divisor == -1:
return MAX_INT

negative = (dividend < 0) != (divisor < 0)
dividend, divisor = map(abs, (dividend, divisor))

bit = 1
while divisor < dividend:
divisor <<= 1
bit <<= 1

r = 0
while bit:
if divisor <= dividend:
dividend -= divisor
r += bit

bit >>= 1
divisor >>= 1

return -r if negative else r``````

• using '*' is not allowed...

• It's just for simplicity for `a` can only be '0' or '1', you can use `if` instead. And for no misunderstanding, I will change it. Thanks anyway.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.