Mockup in C of hardware implementation for multiplication of signed integers

Question

I challenged myself to implement multiplication of signed integers using only +, -, >>, <<, &, |, ^, and conditionals, though I would like to improve my method to not use conditionals if possible in the future. Any input would be very helpful.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include <time.h>

int multiply(int, int);

int main() {
    int a, b, c, i;
    bool equal;

    srand(time(NULL));

    for (i = 0; i < 100; i++) {
        // 0x8000 to ensure no integer overflow is possible
        a = (rand() % 0x8000) * (rand() % 2 ? -1 : 1);
        b = (rand() % 0x8000) * (rand() % 2 ? -1 : 1);
        c = multiply(a, b);
        equal = (c == a * b);

        printf("%-11d * %-11d = %-11d (%s)\n", a, b, c, (equal ? "Success" : "Failure"));

        if (!equal) {
            return EXIT_FAILURE;
        }
    }

    return EXIT_SUCCESS;
}

int multiply(int a, int b) {
    struct {
        unsigned char index : 5;
    } bit;

    int c = INT_MAX & a, // remove sign bit
        d = INT_MAX & b,
        sign = (INT_MIN & a) ^ (INT_MIN & b), // sign of product
        mask = 0x40000000,
        prod = 0;

    bit.index = 30; // keeping track of mask bit index

    do {
        prod += (mask & c ? d << bit.index : 0);
    } while ((bit.index--) && (mask >>= 1));

    return sign | (prod & INT_MAX);
}

Answer 1

Sign bit manipulation unnecessary

I looked at your code and was puzzled by all the sign bit manipulation. As far as I can tell, it's not necessary. I rewrote your function to be like the following and it still passed all your tests:

int multiply(int a, int b)
{
    // Bit keeps track of mask bit index.
    struct {
        unsigned int index: 5;
    } bit = {31};
    int prod = 0;

    do {
        prod += ((a & (1 << bit.index)) ? b << bit.index : 0);
    } while (bit.index--);

    return prod;
}

Bonus answer: no conditionals inside loop

int multiply(int a, int b)
{
    // Bit keeps track of mask bit index.
    struct {
        unsigned int index: 5;
    } bit = {31};
    int prod = 0;

    do {
        prod += (-((a >> bit.index) & 1)) & (b << bit.index);
    } while (bit.index--);

    return prod;
}

Explanation:

1. ((a >> bit.index) & 1) is 1 or 0 depending on the masked bit. Call this B.
2. -B is -1 or 0. This sets up a mask to use for the next step (-1 is a mask of all one bits).
3. -B & (b << bit.index) is either (b << bit.index) or 0.

Answer 2

You know, it's not too bad, but I dislike the magic numbers you have added in place. The mask as 0x40000000 is a problem. int is not a standard size, so why have you set it as 32 bits?

I think you are missing a simple trick here. You are setting the mask high, and decreasing till it's done, when instead, you should start at the low order bits, and increase until there's nothing left to do.... by using a bit-shift (and the mask 1 which is int-size safe.

You have forced the values to be unsigned, so you may do it really easily:

int multiply(int a, int b) {

    int usa = INT_MAX & a, // remove sign bit
        usb = INT_MAX & b,
        sign = (INT_MIN & a) ^ (INT_MIN & b), // sign of product
        prod = 0;

    while (ua && ub) {
        prod += (ua & 1 ? ub : 0);
        ua >>= 1; // shift the multiplicand
        ub <<= 1; // double the multiplier
    }

    return sign | (prod & INT_MAX);
}

This way you resolve the loop faster.

Note that your code has a bug in that it will set 0 * -1 to be INT_MIN... I have reproduced that bug.... it's a problem. You need to check whether one of your values is 0 before returning a sign bit.

How does it work?

We can agree that the product (binary, or decimal): 110 * 101 is the same as 11 * 1010 (halve the first value, double the second - or 1 tenth the first * ten-times the second).

We can also agree that 110 * 101 is the same as 100 * 101 + 10 * 101 + 0 * 101

Butting these logic steps together, we have:

110 * 101 = 100 * 101    + 10 * 101   +  0 * 101
          =   1 * 10100  +  1 * 1010  +  0 * 101
          =   10100      +      1010

If you think of that in binary terms, notice how if the bit is set in the first value, we get the respective two-power of the right-value and add it.

As we shift the left value, we determine whether it's low bit is set, and we multiply it by the doubling right-value... until one of the values is zero.

Answer 3

I've the solution below that a guy showed me time ago (umul_vect()). It's for use with unsigned int, but the printf int the main() seems to indicate that with two's complement negative numbers the results are anyway correct both with signed and unsigned. The generated results suffer (obviously) of overflow when signed negative "small" numbers are used as unsigned! Anyway I leave you the task to manage the cases where the sign is managed in other ways than two's complement.

The umul_base() is classical and uses if, umul_vect uses a vector and doesn't use if except that the while() accomplishes.

I would say you that the practice to avoid conditional jumps not always optimizes the code performance. It's better to evaluate CPU by CPU and to try various kind of compiler optimizations.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef long long unsigned utest; // you may change to use other types

utest umul_vect(utest a, utest b)
{
    utest c[2];

    c[0]=0;c[1]=a;a=0;
    while (b) {
        a+=c[(b & 1)];
        b>>=1;
        c[1]+=c[1];
    }

    return a;
}

utest umul_base(utest a, utest b)
{
    utest res=0;

    while (b) {
        if ( (b & 1) )
            res+=a;
        b>>=1;
        a+=a;
    }

    return res;
}


int main()
{
//Computing a mask that contains an integer with all bit sets to 1
#define MASK(x) ((((x)(1)<<((sizeof(x)<<3)-1))-1)|((x)(1)<<((sizeof(x)<<3)-1)))
#define LIMIT_TYPE short int //You may change to use other types

    utest a,b,i;

    srand(time(NULL));

    for(i=0;i<20;i++) {
        //Limiting int dimension
        a=((LIMIT_TYPE)(rand()&MASK(LIMIT_TYPE)));
        b=((LIMIT_TYPE)(rand()&MASK(LIMIT_TYPE)));
        //unsigned
        puts("Unsigned");
        printf("%llu x %llu = %llu\n",a,b,umul_base(a,b));
        printf("%llu x %llu = %llu\n",a,b,umul_vect(a,b));
        printf("%llu x %llu = %llu\n",a,b,a*b);
        puts("Signed");
        printf("%lld x %lld = %lld\n",a,b,umul_base(a,b));
        printf("%lld x %lld = %lld\n",a,b,umul_vect(a,b));
        printf("%lld x %lld = %lld\n",a,b,a*b);
    }

    return 0;
}