无整数乘法*

Question

我在其中一个站点看到C语言中的一个采访问题，要求您编写一个函数，该函数可以获得2个整数，num和times，并且可以不使用*运算符来对它们进行乘法运算，这意味着主要使用shift左和右。我想出了一个可行的答案（除非有人发现一个bug），但是有没有人有更好的方法来解决它在更好的时间或内存消耗？

这里是我写的：

#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

这里有一个更简洁，bugfree（我相信）执行，甚至不发生未定义行为：

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; - >这将返回0的数字，它们的二进制表示中不共享至少一个共同幂2，即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在另一篇文章的大部分算法实现]