Note that In fact, we have
This fact is useful in performing integer division. We can compute divided by by recursion (note the summation sign above). Consider , we have
Since , , if is a power of 2, we can perform the div and mod operations by bit shift.
def div(m, n):
# n+1 is 2^k assumed here
result = 0
A = m
while (True):
A = A >> k
B = A & n
result = add(result, A)
if A <= n:
break
if A == n: result = result + 1
return result
def add(A, B):
result = A XOR B
carry = (A AND B) << 1
return add(result, carry) if carry else result