2 minute read

Multiply without arithmetic - Elements of Programming Interviews (EPI)

Problem:

Write a program that multiplies two nonnegative integers. The only operators allowed are:

  • Assignment
  • Bitwise operators >> << | & ~ ^
  • Equality checks and Boolean combinations \(x>y\) and increments are not allowed either.

Solution:

The brute force approach would be to add \(x\) to itself \(y\) times. This can have time complexity of upto \(O(2^n)\) where \(n\) is the number of bits in input.

We can take advantage of the multiplication algorithm we normally use to calculate products manually where we multiply x by first digit of y and then shift x by a factor of 10 and add it to the result. We take this same approach with binary multiplication and instead of shifting by 10 we shift x one bit to the left i.e by a factor of 2. for example:

  • 1011 * 110 can be done by computing the sum of 1011*0 + 10110*1 + 101100*1.
  • Here we add x shifted over by 1 bit to a running sum based on the bits in y. In other words we add \(2^k x\) to the result if the \(k_{th}\) bit of \(y\) is 1.

Since we dont have arithmetic operations we have to implement our own add function and then implement multiply as follows:

    
def add(a: int, b: int) -> int:
    """Function to add 2 integers using binary operations only""" 
    carry = 0
    result = 0
    # These will just act as counters
    tmp_a, tmp_b = (a, b)
    current_bit = 1
    while tmp_a or tmp_b:
        a_k = a & current_bit  # Extract kth bit of a
        b_k = b & current_bit  # Extract kth bit of b
        result |= a_k ^ b_k ^ carry  # Add to running sum: XOR works because it will give 1 if all 3 are 1, it will give 0 if any 2 are 1. and 1 otherwise.
        carry = (a_k & b_k) | (a_k & carry) | (b_k & carry)  # set next value of carry forward if any 2 values are 1s then we need to carry forward.
        carry, current_bit = (carry << 1, current_bit << 1)
        tmp_a, tmp_b = (tmp_a >> 1, tmp_b >> 1)  # pseudo counter for loop
    return result | carry


def multiply(x: int, y: int) -> int:
    """Function to multiply 2 integers using binary operations only"""
    res = 0
    while y:
        if y & 1:
            res = add(res, x)
        x, y = x << 1, y >> 1
    return res