1. ## Hodor Can Multiply

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

Code:
```/*
* Function to multiply two integers without using the * or / operators.
* Uses the "Egyptian Method" of multiplication.
*
* By Hodor, 2013
*
*/
#include <stdio.h>
#include <assert.h>

#define ZMIN(a,b)   ( (a) < (b) ? (a) : (b) )
#define ZMAX(a,b)   ( (a) > (b) ? (a) : (b) )
#define ZABS(n)     ( (n) < 0 ? (-n) : (n) )

long multiply(int a, int b);

int main(void)
{
int i, j;
for (i = -6000; i < 6000; i++)
for (j = -6000; j < 6000; j++)
assert(multiply(i,j) == i*j);

return 0;
}

long multiply(int a, int b)
{
unsigned short aneg = a < 0, bneg = b < 0;
unsigned long total = 0;
unsigned long c = ZMIN(ZABS(a), ZABS(b)),
d = ZMAX(ZABS(a), ZABS(b));

while (c > 0) {
total += c & 1 ? d : 0;
c >>= 1;
d <<= 1;
}

return aneg ^ bneg ? -total : total;
}```

2. 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...

3. 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). There may be a corner case involving negative numbers, but my brain is too fried to work that out at the moment...
That's exactly what I'm unsure about as well. Possibly sleep will help

4. Actually, thinking about it I don't think overflow can possibly occur (with the same assumptions you stated).

5. 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.

6. 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.

7. 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".

8. You're right. Thanks.

9. It appears you have your "!=" logic backwards in your example

 Never mind, seems you realized this.

10. Originally Posted by Matticus

 Never mind, seems you realized this.
Yeah, sorry.

11. Code updated

Code:
```/*
* Function to multiply two integers without using the * or / operators.
* Uses the "Egyptian Method" of multiplication.
*
* By Hodor, 2013
*
*/
#include <stdio.h>
#include <assert.h>

#define ZMIN(a,b)   ( (a) < (b) ? (a) : (b) )
#define ZMAX(a,b)   ( (a) > (b) ? (a) : (b) )
#define ZABS(n)     ( (n) < 0 ? (-n) : (n) )

long multiply(int a, int b);

int main(void)
{
int i, j;
for (i = -6000; i < 6000; i++)
for (j = -6000; j < 6000; j++)
assert(multiply(i,j) == i*j);

return 0;
}

long multiply(int a, int b)
{
unsigned short aneg = a < 0, bneg = b < 0;
unsigned long total = 0;
unsigned long c = ZMIN(ZABS(a), ZABS(b)),
d = ZMAX(ZABS(a), ZABS(b));

while (c > 0) {
total += c & 1 ? d : 0;
c >>= 1;
d <<= 1;
}

return aneg != bneg ? -total : total;
}```

12. 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;
}```

13. Originally Posted by rcgldr
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.
Nice!

14. There must be super special trick to make p not always equal to zero, but I don't see it.

15. In hardware, the sign extension can be avoided by manipulating the bits. (note, this is still a signed multiply, the unsigned variables are used to avoid sign extension).

Code:
```#include <stdio.h>

unsigned int multiply(unsigned short m0, unsigned short m1)
{
unsigned int i, p;
p = 0x10000;
for(i = 0; i < 15; i++)
p += ((m1 & (1<<i)) ? ((unsigned)m0 ^ 0x8000) : 0x8000)<<i;
p += ((m1 & (1<<i)) ? ((unsigned)m0 ^ 0x17fff) : 0x17fff)<<i;
return p;
}

int main(){
char buffer[80];
unsigned 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((unsigned short) m0, (unsigned short) m1));
}
return 0;
}```
Wiki article:

Binary multiplier - Wikipedia, the free encyclopedia