Python The Challenge: Weird Multiplication. “Russian Peasant” or “Ancient Egyptian” method for multiplication.

Question

The algorithm is as follows: If A and B are the 2 integers (only integers) to be multiplied, we repeatedly multiply A by 2 and divide B by 2, until B cannot be divided any further, that is, until its value becomes 0 (remember, this is integer division). During each step, whenever B is an odd number, we add the corresponding A value to the product we are generating. In the end, the sum of the A values that had corresponding odd B values is the product.

Answer 1

If you want to create a challenge, please follow the instructions in the top of this thread:
https://www.sololearn.com/Discuss/1270852/?ref=app

Why only Python? I think, if you let the participants choose the languages themselves, they will be more likely to submit a code...

Answer 2

Taking some of the mystery out of it, that algorithm is how you multiply in base 2.
Each time you multiply A by 2, it shifts A by one place (i.e., one bit) leftward.
Dividing B by 2 shifts B one place (bit) rightward.
If B is odd, that means its lowest bit is 1 so you would add 1*A (or simply A).
If B is even, then its lowest bit is 0 so you would add 0*A (or simply 0, therefore you may skip the addition).

It is the same procedure as decimal long-hand multiplication, except done in binary.