Thread: Hodor Can Multiply

Originally Posted by Hodor

I'm think about adding a test for overflow but not 100% sure.

Assuming sizeof(long) > sizeof(int), that shouldn't be necessary (since the result of the multiplication two N-bit numbers can never exceed 2N bits). There may be a corner case involving negative numbers, but my brain is too fried to work that out at the moment...

Originally Posted by Sebastiani

Assuming sizeof(long) > sizeof(int), that shouldn't be necessary (since the result of the multiplication two N-bit numbers can never exceed 2N bits).

The catch is that sizeof(long) can be equal to sizeof(int).

Originally Posted by Sebastiani

There may be a corner case involving negative numbers, but my brain is too fried to work that out at the moment...

The "corner case" you need to worry about if abs(INT_MIN) exceeds abs(INT_MAX), and if you are multiplying by one of them. That is practically quite common.

In terms of the OP, I don't tend to be in favour of using bitshift operations as a shortcut to multiplication or division by two. Yes, I know they are equivalent on unsigned types. But it is clearer to do what you mean (i.e. your code is working to achieve a numeric result, so it is clearer to use numeric operations) and most modern compilers will pick the fastest operation possible (i.e. you are indulging in premature optimisation).

And using xor (^ operator) to check for inequality is hideous.

Originally Posted by grumpy

In terms of the OP, I don't tend to be in favour of using bitshift operations as a shortcut to multiplication or division by two. Yes, I know they are equivalent on unsigned types. But it is clearer to do what you mean (i.e. your code is working to achieve a numeric result, so it is clearer to use numeric operations) and most modern compilers will pick the fastest operation possible (i.e. you are indulging in premature optimisation).

Note that I set myself the restriction not to use * or /. I admit that using the bitshift operators is (probably) a bit of a cheat. It's safe as you say, but anyway. To multiply d by two I can change the code to d += d. That's easy enough. To divide c by 2, though, I'd probably have to do something like

Code:

        count = 0;
        while (c > 1) { /* Divide c by 2 */
            count++; 
            c -= 2;
        }
        c = count;

Which I guess has advantages applicable to my original goal, but it's obviously going to be slower. Maybe there's another way to divide something by 2 that I don't know of?

Originally Posted by grumpy

And using xor (^ operator) to check for inequality is hideous.

It's not checking for inequality. Two numbers multiplied together give a negative answer if only ONE (but not both) of the operands are negative; and this is, well, what XOR does.

Originally Posted by Hodor

It's not checking for inequality. Two numbers multiplied together give a negative answer if only ONE (but not both) of the operands are negative; and this is, well, what XOR does.

Either you are bluffing or you don't understand your own code.

aneg and bneg are unsigned shorts initialised with values 0 or 1 (the result of expressions "a < 0" and "b < 0", respectively). The expression aneg ^ bneg therefore produces the same result as "aneg != bneg".

You're right. Thanks.

signed 16 bit by 16 bit multiply producing 32 bit product code example, using classic method. (shorts are assumed to be 16 bit, ints are assumed to be 32 bit). Note that casting short to int extends the sign bit. For faster speed, this could be done only once.

Code:

#include <stdio.h>

int multiply(short m0, short m1)
{
int i, p;
    p = 0;
    for(i = 0; i < 15; i++)
        if(m1 & (1<<i))
            p += (int)m0 << i;
    if(m1 & (1<<i))
        p -= (int)m0 << i;
    return p;
}

int main(){
char buffer[80];
int m0, m1;
    while(1){
        printf("enter numbers in hex: ");
        fgets(buffer, sizeof(buffer), stdin);
        if(2 != sscanf(buffer, "%x %x", &m0, &m1))
            break;
        printf("product is: %x\n", multiply((short) m0, (short) m1));
    }
    return 0;
}