CODEWITHSUNDEEP
pythonalgorithmbinarybit-manipulationbitwise-operators
VickTree
VickTree

Reputation: 909

Compute x/y without Arithmetical Operators

I am going through the "Elements of Programming Interview" in python currently and have gotten stuck at this part. The code below is simply multiplies two numbers without using any operators; the explanation given by the authors is below:

We can compute the largest k such that (2^k)y <= x, subtract (2^k)y from x, and add 2^k to the quotient. For example is x = (1011) and y =(10), then k = 2, since 2 x 2^2 <= 11 and 2 x 2^3 > 11. We subtract (1000) form (1011) to get (11), add 2^k = 2^2 = (100) to the quotient, and continue by updating x to (11).

A better way to find the largest k in each iteration is to recognize that it keeps decreasing. Therefore, instead of testing in each iteration whether (2^0)y, (2^1)y, (2^2)y, ... is less than or equal to x, after we initially find the largest k such that (2^k)y <= x, in subsequent iteration we test (2^k-1)y, (2^k-2)y, (2^k-3)y, ... with x. For the example given earlier, after setting the quoient to (100) we continue with (11). Now the laegest k such that (2^k)y <= (11) is 0, so we add 2^0 = (1) to the quotient, which is now (101). We continue with (11) - (10) = (1), Since (1) 

def divide(x, y):

    result, power = 0, 32
    y_power = y << power

    while x >= y:

        while y_power > x:

            y_power >>= 1
            power -= 1

        result += 1 << power
        x -= y_power

    return result

My Questions are:

  1. How is the algorithm working (overview)
  2. whey does power = 32
  3. why are we shifting y by power (32)
  4. what does y_power represent
  5. why are we adding 1 << power to result

Upvotes: 2

Views: 457

Answers (1)

Corylus
Corylus

Reputation: 889

This is long division for binary numbers. You probably learned this for decimal numbers in school.

If we want to divide x by y we ask our self "how many times does y fit into x if we add as many zeros to it as possible?". Adding n zeros to y is equivalent to multiplying with 2^n or shifting left by n. 

power = 32
y_power = y << power

The first guess of the algorithm is to add 32 zeros to y, which is shifting it left with power. So, if you know your result might be >= 2^33, you would have to use a larger initial value for power. 

while y_power > x:
   y_power >>= 1
   power -= 1

In the inner loop it will test if y_power already fits into x and if not, will "move it one digit to the right". 

result += 1 << power

When this is done, it will just write the "number of how many times y shifted left fits into x" to the result. As in binary numbers this can just be zero or one and the inner loop skipped all zeros, this must be one. 

x -= y_power

As you know from long division, we now need to subtract this multiple of the divisor, y, from the dividend and continue with the result.

while x >= y:

We will stop if this difference, y, is smaller than x and it is therefore impossible for 2^power * y to fit into x.

Example Let's calculate 15/5:

 1111 / 101 = 11
-1010
------
  101
 -101
------
    0

We have x=1111 and y=101 and start with with power=1 for brevity. First we calculate y_power = y<<power = 101<<1 = 1010. As 1010 > 1111 is false we skip the inner loop and add 1<<power = 1<<1 = 10 to the result. Then we subtract y_power = 1010 from x = 1111 and get 101. Now y_power = 1010 > 101 = x is true and we decrement power, so we get power = 0 and y_power = y<<power = 101. Now y_power>xis false again and we add 1<<power = 1 to our result and get x - y_power = 0. Now x >= y is false and we are finished with result = 11.

Upvotes: 3

Related Questions