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:
    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