2 minute read

Division with Bit shifting - Elements of Programming Interviews (EPI)

Problem:

Given 2 positive integers, compute their quotient, using only +, -, >>, <<. Compute \(\frac{x}{y}\).

Solution:

The naive/brute force solution is to keep adding \(y\) to itself until we exceed \(x\) and count the number of additions which will be our quotient.

A way to speed up the brute force solution would be to take larger steps the way we do long division by guessing an integer just large enough so that we can multiply it by our divisor(?) and get a new number after subtracting. Then we try to guess another integer for this number and so on. We can implement this manual algorithm in our division by using the shifting to multiply by powers of 2. Find the largest power of 2 that we can multiply our \(y\) such that it is smaller than \(x\). Add this number to our quotient and then repeat with a new \(x\) now set as the difference : \(x = x - y*2^k\). An example illustrates this process a lot more concretely.

Example:

\[x = 129 \\ y = 17 \\ q = 0\]
  • After looping we find that the highest power of 2 we can multiply \(17\) with, is the number \(4=(2^2)\). Since \(17*4 = 68\) and \(17*8 = 136\) which exceeds \(x=129\).
  • We add \(2^2 = 4\) to our quotient \(q = q + 4 = 4\)
  • Now we set \(x = 129 - 68 = 61\).
  • We now find \(17*2 = 34\) since \(17*4 = 68\) which exceeds \(x=61\).
  • We add 2 to quotient \(q = q + 2 = 6\)
  • We set \(x = 61 - 34 = 27\)
  • We now find \(17*1 = 17\) since \(17*2 = 34\) which exceeds \(x=27\).
  • We add 1 to quotient \(q = q + 1 = 7\)
  • We set \(x = 27 - 17 = 10\)
  • This \(x\) is now smaller than \(y\) so we have found our quotient \(q = 7\).
  • Proof : \(17*7 = 119\) and \(17*8 = 136\)

In Code :

def divide(x: int, y: int) -> int:
    """Function to find largest quotient such that y * quotient <= x
    This is the same as x/y"""
    quotient = 0
    while x >= y:
        tmp = y
        k = 0
        # find largest k such that 2^k * y <= x
        while tmp <= x:
            # shift by k is the same as multiplying by 2*k
            tmp <<= 1
            k += 1
        quotient += (1 << (k-1))  # This is k-1 because the loop exits after adding 1.
        x = x - (y << (k-1))  # set x to be x - y * 2^k
    return quotient