Multiply two integers without using any arithmetic operators

Question

I've managed to add and subtract two integers without using any arithmetic operators. I've tried multiply ways to multiply two integers together but can't seem to make any progress. How can I multiply two integers without using any arithmetic operators? The arithemtic operators you can't use are (+, ++, +=, -, --, -=, ∗, /, %). Also from the directions that were given is to "take lowest 16 bits of the product should be stored in product, and the full product should be stored in full_product as a 32-bit value." The commented out lines in the method are there to show you what not to do. Thanks! Here is the code done in C

#include "alu.h"

/* Adds the two arguments and stores the sum in the return structure's result
 * field.  If the operation overflowed then the overflow flag is set. */
addition_subtraction_result add(uint16_t augend, uint16_t addend) {
    addition_subtraction_result addition;
    while (addend != 0){
      int carry = augend & addend;
      augend = augend ^ addend;
      addend = carry << 1;
    }
    addition.result = augend;
    //addition.overflow = false;
    return addition;
}

/* Subtracts the second argument from the first, stores the difference in the
 * return structure's result field.  If the operation overflowed then the
 * overflow flag is set. */
addition_subtraction_result subtract(uint16_t menuend, uint16_t subtrahend) {
    addition_subtraction_result subtraction;
    while (subtrahend != 0 ){
      int borrow = (~menuend) & subtrahend;
        menuend = menuend ^ subtrahend;
        subtrahend = borrow << 1;
    }
    subtraction.result = menuend;
    return subtraction;
}

/* Multiplies the two arguments.  The function stores lowest 16 bits of the
 * product in the return structure's product field and the full 32-bit product
 * in the full_product field.  If the product doesn't fit in the 16-bit
 * product field then the overflow flag is set. */
multiplication_result multiply(uint16_t multiplicand, uint16_t multiplier) {
    multiplication_result multiplication;
    //multiplication.product = multiplicand * multiplier;         // THIS IS DISALLOWED
    //multiplication.full_product = multiplicand * multiplier;    // THIS IS DISALLOWED
                          
    multiplication.product = multiplicand;
    multiplication.full_product = multiplicand;
    return multiplication;
}

https://stackoverflow.com/questions/6857382/multiplication-in-c-without-arithmetic-operators — Retired Ninja, Mar 02 '21 at 04:21
"I've tried multiply ways to multiply two integers together but can't seem to make any progress" --> It is useful if you posted at least one of those. — chux - Reinstate Monica, Mar 02 '21 at 10:59

score 1 · Answer 1 · answered Mar 02 '21 at 04:30

General idea (types are deliberately incorrect to you can't copy/paste this back in):

uint16_t multiply(uint8_t multiplicand, uint8_t multiplier)
{
    uint16_t result = 0;
    for (int i = 0; i < CHAR_BIT * sizeof(multiplier); i++)
        if (multiplier & (uint8_t))
            result = add(result, (uint16_t)multiplicand << (uint16_t)i);
    return result;
}

But this won't work for you yet because because you don't have long add yet. We need to decompose long add like this:

uint16_t addlong(uint8_t addend1a, uint8_t addend1b, uint8_t addend2a, uint8_t addend2b)
{
    struct addend_result a = add(addend1a, addend2a);
    struct addend_result b = add(addend2a, addend2b);
    if (a.carry) b = add(b.result, 1);
    return a.result | ((uint16_t)b.result << 8);
}

So these are the pieces required to build. Adapt them to the framework you actually have and the type widths you actually have.

You have to unroll the for loop in multiply because of silliness. This means you get 16 lines because your input size is 16 bits.

Typo in `if (multiplier & (uint8_t))` (should be `if (multiplier & (uint8_t)1)`). The loop itself could be more like `while(multiplier != 0) {` and `multiplier >>= 1; multiplicand <<= 1;` to avoid the need for `i` and the (disallowed) `i++`. — Brendan, Mar 02 '21 at 05:33

Multiply two integers without using any arithmetic operators

1 Answers1