3
\$\begingroup\$

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);
}
\$\endgroup\$
7
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Does this fix the bug @rolfl observed? \$\endgroup\$ – Patrick Roberts May 15 '15 at 23:05
  • \$\begingroup\$ @PatrickRoberts As a matter of fact it did. \$\endgroup\$ – JS1 May 15 '15 at 23:05
  • \$\begingroup\$ Thank you very much, this looks a lot simpler than what I had. \$\endgroup\$ – Patrick Roberts May 15 '15 at 23:06
  • \$\begingroup\$ WOW! Very impressive. I wish I could upvote you twice. \$\endgroup\$ – Patrick Roberts May 15 '15 at 23:15
  • \$\begingroup\$ Hmmm... I retracted my +1... I don't like that it always does 31 loops, even for 1 * 1, and I dislike that it is not-portable (32-bit int). In effect, the algorithm is sacrificing some aspects to avoid a sign, and instead of doing a branch (if), it does a negate, and AND, and it does just as many shifts. The struct is also completely unnecessary.... and confusing. I am going to run some time tests... see if there's anything to my concerns. \$\endgroup\$ – rolfl May 16 '15 at 0:45
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ See the note on the bug \$\endgroup\$ – rolfl May 15 '15 at 22:55
  • \$\begingroup\$ Thank you very much, I didn't notice that bug. Can you elaborate a little more on how your while loop works? First of all, I'm assuming you meant to use usa and usb rather than ua and ub, but that aside, what's going on is a little confusing to me. \$\endgroup\$ – Patrick Roberts May 15 '15 at 22:58
  • \$\begingroup\$ add explanation \$\endgroup\$ – rolfl May 16 '15 at 0:23
2
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ @Patrick Roberts. I would like your opinion! Remember that the assumption of sign is important with CPUs that doesn't use two's complement. \$\endgroup\$ – Sergio Formiggini May 16 '15 at 9:07
  • \$\begingroup\$ My argument to avoid conditionals wasn't to necessarily optimize, but to make the task arithmatically translatable to hardware. Also, I thought the point of CR was to give a review of the OP's code without modifying the expected behavior, which you seem to have done with your answer. \$\endgroup\$ – Patrick Roberts May 16 '15 at 17:47
  • \$\begingroup\$ Ok! I've understand something about software, I apologize! ... I didn't think it was an hardware problem ... My solution doesn't use conditional jumps, but I understand your point of view! \$\endgroup\$ – Sergio Formiggini May 16 '15 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.