Why this division algorithm works?
For even $a$ and $b \ne 0$ and integral division
$$ \frac{a}{b} = \frac{2a}{2b} = 2 \cdot \frac{( a / 2 )}{b} $$
Similarly for the remainder
$$a = 2 \cdot \frac{a}{2} \space (mod \space b)$$
Effectively transforming your problem of division of number with n bits into division of a number with n-1 bits (half as big number).

The algorithm uses integral division in the floor(x\2) part and there you might lose 1 if x was odd. You're giving it back with the if x is odd: block to the remainder and since this might make your reminder the same size as y you need to check if that happened and change the values accordingly. (Notice that r &gt; y can never happen and there could be just as fine if r == y:.)

You just do this n times where n is the number of bits of x.

Finally the algorithm is not $O(n^2)$ but rather $O(n)$ in the number of bits of x. That's assuming the floor(x/2) part does not call the divide function, because that would end in infinite loop (you would need e.g. compute a/2 to compute a/b which would in turn need again computation of a/2. This can be avoided by using a&gt;&gt;1 instead of a/2 which also authomatically floors the result).