I don’t understand how your solution works for an input like 37/3:
Dividend Divisor Quotient Temp
37 3 1 3
37 3 2 6
37 3 4 12
37 3 8 24
37 3 16 48
When the answer should be 12
Hi Hasan_Zaidi,
Basically, the steps you have mentioned above is the first part of the algorithm. Here, the quotient is now 16, while the value is 48.
We can see in the code that after the while loop, there is an if condition. The program only goes into this if when val is bigger than x. In our case, 48 > 37.
This is where the first recursive call is made. val and q are divided by 2 (right shift). q = 8 and val = 24.
Now the function is called on (37-24, 3) which is (13, 3). The result of this is will be added to q which is 8.
If you make a dry run, the recursive call returns 4.
8 + 4 = 12. Hence, integer_divide(37, 3) = 12.
Let us know if you have any further questions.
Regards,
Coderust