32 位的有符号整数_再试计算32位整数中1的个数

前几天看到这篇文章，挺有意思。

然后在gd32f350开发板上把各种算法都试了一遍，消耗时钟周期数如下：

1. 原文的算法：

  register int xx=x;
  xx=xx-((xx>>1)&0x55555555);
  xx=(xx&0x33333333)+((xx>>2)&0x33333333);
  xx=(xx+(xx>>4))&0x0f0f0f0f;
  xx=xx+(xx>>8);
  return (xx+(xx>>16)) & 0xff;

这个最快，23个时钟周期。

2. 原文作者自创算法：

        int i = 0;
	int s = 0;
	for(i = 0;i<32;i++)
	{
		if(x&0x01)
			s ++;
		x = x>>1;
	}
	return (s);

这个最直白，不过性能差远了，需要205个时钟周期。

3. 上述算法，循环体全部展开，134时钟周期。

4. 上述算法，把if(x&1) s++改成s+=(x&1)，不做循环展开，需要236周期，比原先还慢。

5. 再对4作循环体展开，降到73周期了。

6. hakemem算法：

    unsigned long tmp;
    tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
    return ((tmp + (tmp >> 3)) & 030707070707) % 63;

很简洁吧？根据输入，从29-38周期不等，还是没有第一个快。

7. dense算法：

  int count = 8 * sizeof(unsigned int);
    n ^= (unsigned int) -1;
    while(n) {
        --count;
        n &= (n - 1);
    }
    return count;

根据输入，从16到208周期不等，最快时比第一个快，但是平均下来就不行了。如果输入数据比较特殊，也许能发挥优势。

今天继续，在stm32f030上再试的结果，7个算法消耗的时钟周期数分别是25 324 168 334 96 60-255 11-267。

又增加了查表算法，把0x00~0xff里1的个数存成表格，对32位拆成4个8位分别查表再相加：

    return tab[x&0xff] + tab[(x >> 8) & 0xff] + tab[(x >> 16) & 0xff] + tab[x >> 24];

结果是29个时钟周期，比第一个算法稍慢一点。

不过这里查表的方式似乎还可以再优化一点：

typedef unsigned char u8_t;
#define b0(x)    ((( struct { u8_t b0,b1,b2,b3; } *)(&x))->b0)
#define b1(x)    ((( struct { u8_t b0,b1,b2,b3; } *)(&x))->b1)
#define b2(x)    ((( struct { u8_t b0,b1,b2,b3; } *)(&x))->b2)
#define b3(x)    ((( struct { u8_t b0,b1,b2,b3; } *)(&x))->b3)

然后

    return tab[b0(x)] + tab[b1(x)] + tab[b2(x)] + tab[b3(x)];

这样避免了不必要的移位运算，应该能再快点。结果是25个时钟周期，和第一个算法完全一样了。(查表居然没有更快？)

用stm32f401开发板再试，结果是17 235 157 238 85 21-30 16-210 24/22。怎么回事，dense的最快结果比stm32f030还慢了？考虑到可能是开了PLL，FLASH访问延迟会稍微影响一点性能。

把PLL关掉再试，结果是17 232 160 231 95 23-32 12-204 22/20。除了dense，查表法也都快了两个时钟周期，但是前面有些算法又慢了一点。可能是关PLL之后f4的流水线没有发挥作用？

再找出stm32f103开发板，再试，开PLL的情况是17 305 185 299 95 30-39 17-161 40/44，没想到不但整体不如f401，个别情况连f030也不如了，特别是查表的两种方式，用匿名结构体成员的方式反倒慢了。有空得看看汇编这里是怎么处理的。

关PLL，结果是17 235 158 231 95 23-32 12-204 20/26，果然全面提升了。(按时钟周期计，实际上开PLL的话主频高了N倍，按时间计算还是快得多。)

总结，还是第一个算法最快，包括查表在内的其他各种算法顶多能在个别情况下领先或者持平。