这是知乎上另一位高手实现的,原为c++,我改为c。完全使用左右位移方法完成32位乘法,我当初也是想用位移实现,只是没找到算法,这个代码看的有点晦涩,但确实达到了目的,并且比递归更能符合题意(递归的短路算法在汇编级肯定有条件判断跳转的)。
#include <stdio.h>
int mul(int n,int m)
{
int c[2] = { 0, n };
#define BITMUL(i) (c[ 1 & ((m) >> (i))]<<(i)) //m第i位乘n
#define BYTEMUL(i) (BITMUL((i<<3))+BITMUL((i<<3)+1)+BITMUL((i<<3)+2)+BITMUL((i<<3)+3)+BITMUL((i<<3)+4)+BITMUL((i<<3)+5)+BITMUL((i<<3)+6)+BITMUL((i<<3)+7))//m第i字节乘n
#define INTMUL()
(BYTEMUL(0)+BYTEMUL(1)+BYTEMUL(2)+BYTEMUL(3)) //m乘n
return INTMUL();
#undef BITMUL
#undef BYTEMUL
#undef INTMUL
}
int f(int n)
{
return mul(n, n + 1) >> 1;
}
void main()
{
printf("%d\n",f(100));
}