c - 不带 * 的整数乘法

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 语言中，符号位的移位是未定义的行为——您需要为此任务使用无符号整数。

Answer 2

如果您想要一个有符号整数变体，这将起作用：

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;
}

[归功于 H2CO3 在另一篇文章中对大部分算法的实现]