compute x * y without arithmetical operators

Question

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

"The algorithm taught in grade-school for decimal multiplication does not use repeated addition-it uses shift and add to achieve a much better time complexity. We can do the same with binary numbers-to multiply x and y we initialize the result to 0 and iterate through the bits of x, adding 2ky to the result if the kth bit of r is 1. The value (2^k)*y can be computed by left-shifting y by k. Since we cannot use add directly, we must implement it. We apply the grade-school algorithm for addition to the binary case, i.e., compute the sum bit-by-bit, and "rippling" the carry along."

def multiply(x, y):
    def add(a, b):
        running_sum, carryin, k, temp_a, temp_b = 0, 0, 1, a, b

        while temp_a or temp_b:
            ak, bk = a & k, b & k
            carryout = (ak & bk) | (ak & carryin) | (bk & carryin)
            running_sum |= ak ^ bk ^ carryin
            carryin, k, temp_b, temp_b = (
                carryout << 1, k << 1, temp_a >> 1, temp_b >> 1)

        return running_sum | carryin

    running_sum = 0
    while x:  # Examines each bit of x
        if x & 1:
            running_sum = add(running_sum, y)
        x, y = x >> 1, y << 1

    return running_sum


print(multiply(2, 2))

My Questions are:

1. what is the purpose of the variable "ak" and "bk"
2. what is happening with the carryout vvariable; why are we using bitwise-and operator for (ab & bk, ak & carrying and bk & carryin) and then using bitwise-or?
3. how is the variable "running_sum" keeping track of the sum by using bitwise-XOR and bitwise-OR?
   4. why are we returning "running_sum | carryin"

Any assistance in understanding this code would be appreciated. Thanks in advance.

Answer 1

in add, we're adding two binary numbers, bit-by-bit.

• k is the bit we're looking at.
• ak and bk are the values of k-th bit of a and b
• carry for the next digit will be 1, if at least two out of previous ak, bk, or previous carry (carryin) is 1. Hence, carryout = (ak & bk) | (ak & carryin) | (bk & carryin)
• in k-th digit, we get 1 if odd number of ak, bk, or carryin is 1. Hence, ak ^ bk ^ carryin. Since we're getting only one bit, we can add it to running_sum by applying OR.
• finally, when a and b are exhausted (we reached their most significant bits), we still need to take care of potentially remaining carry flag. Thus, running_sum | carryin.