整数乘法没有*

Question

我在其中一个网站上看到了C中的一个面试问题,你被要求编写一个函数,该函数得到2个整数,num和times,并且不使用*运算符多个,这意味着主要使用左右移位.我提出了一个有效的答案(除非有人发现了一个错误),但是有没有人有更好的方法在更好的时间或内存消耗中解决它？

这是我写的:

#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");
}

？

Answer 1

这是一个更简洁,无错误(我相信)的实现,甚至不会调用未定义的行为:

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

你的代码有几个缺陷:

1. 可读性,长度等......
2. if ((num & times) == 0) return 0;- >对于其二进制表示中不共享至少一个2的公共幂的数字,这将返回0,即4 * 8 = 0.
3. 在符号位中移位是C中未定义的行为 - 您需要使用无符号整数来执行此任务.