Integer multiplication without *

Question

I saw in one of the sites an interview question in C, which you are asked to write a function which get 2 integers, num and times, and multiple them without using the * operator, meaning using mainly shift left and right. I came up with a working answer (unless anyone finds a bug), but does anyone has a better way solving it in better time or memory consumption?

here is what I wrote:

#include <stdio.h>

int multiply_with_shift (int num, int times)
{
   int cnt=0;
   int org_times=times;
   if((num & times)==0)
       return 0;
   else
   {
   while(times >1)   
   {
      times=  times >> 1;
      cnt++;
   }
   int val= 1;
      val= val <<cnt;              
   int sub= org_times-val;         
   int res= num << cnt;            
   for( int i=0 ; i < sub; i++)    
   {
      res+=num;
   }
      return res;
   }
}


void main()
{
    int tmp;
    tmp=multiply_with_shift(5,15);
    printf(" the answer is : %d \n", tmp);
    printf("\n");
}

?

Might get better answers over here: http://codereview.stackexchange.com/ — fire.eagle, Feb 13 '13 at 14:14
I agree with fire.eagle. BTW, this -> `if((num & times)==0)` should be `if((num && times)==0)` — MByD, Feb 13 '13 at 14:15
@H2CO3 - I think both will work (although yours prettier :) ) — MByD, Feb 13 '13 at 14:26
This is duplicate question :http://stackoverflow.com/questions/4456442/interview-multiplication-of-2-integers-using-bitwise-operators — One Man Crew, Feb 13 '13 at 14:53

score 5 · Answer 1 · 2013-02-13T14:30:13.920

5

Here's a more concise and bugfree (I believe) implementation, that doesn't even invoke undefined behavior:

unsigned mul(unsigned a, unsigned b)
{
    unsigned acc = 0;
    while (b) {
        if (b & 1) acc += a;
        b >>= 1;
        a <<= 1;
    }
    return acc;
}

Your code had several flaws:

readability, length, etc...
if ((num & times) == 0) return 0; -> this would return 0 for numbers of which don't share at least one common power of two in their binary representation, i. e. 4 * 8 = 0.
Shifting in the sign bit is undefined behavior in C - you need to use unsigned integers for this task.

edited Feb 13 '13 at 14:30

answered Feb 13 '13 at 14:21

`` *The comments under this answer were obsolete, or pure noise and have subsequently been removed. Please keep comments constructive, professional and on topic.* – Tim Post Feb 13 '13 at 15:34
1

@TimPost OneManCrew accused me of something I didn't do. That's unfair. – Feb 13 '13 at 15:42
@H2CO3 I realy liked your answer, couldn't find a bug and it deals with all kinds of integers such as 2^n and zero. do you have any idea how to deal with signed integers also? – KBE Feb 14 '13 at 13:25
@KBE MatsPetersson's solution deals with signed integers as well (but you can just XOR `a < 0` and `b < 0` anyway). – Feb 14 '13 at 13:57

Mats Petersson · Answer 2 · 2013-02-13T15:35:34.763

0

If you want a signed integer variant, this would work:

int mul(int a, int b)
{
    sign = (a ^ b) >> (sizeof(a) * CHAR_BIT - 1);
    if (a > 0)
        a = -a;
    if (b > 0)
        b = -b;
    int acc = 0;
    while (b) {
        if (b & 1) acc += a;
        b >>= 1;
        a <<= 1;
    }
    if (sign) acc = -acc;
    return acc;
}

[Credit to H2CO3's implementation in another post for most of the algorithm]

edited Feb 13 '13 at 15:35

answered Feb 13 '13 at 14:41

Mats Petersson

126,704
14
140
227

1

Then it needs to return `int`, right? :) – Feb 13 '13 at 14:43
Yes, typical copy'n'paste error. – Mats Petersson Feb 13 '13 at 14:46
This doesn't work. `a &= ~SIGN` is not the correct way to take the absolute value on 2's complement systems. – interjay Feb 13 '13 at 14:50
Of course it isn't. Can you tell it's been a while since I last did this sort of stuff? ;) – Mats Petersson Feb 13 '13 at 14:53
@MatsPetersson I believe XOR-ing `a >> (sizeof(a) * CHAR_BIT - 1)` and `b >> (sizeof(b) * CHAR_BIT - 1)` would be good. – Feb 13 '13 at 15:32
I did something like that - but only one shift... – Mats Petersson Feb 13 '13 at 15:35

Integer multiplication without *

2 Answers2