向“世界上最快的判断32位整数二进制中1的个数的算法”挑战

connet

const int one_in_char[256]=
{
    0, 1, 1, 2, 1, 2,2,3
......
                              ,8
}
此为 0-255 每个数中 1 的个数。
这个雕虫小技在密码，crc...等地方使用很广泛。
int func2(int v)
{
    int n=v;
    unsigned char *ptr=(unsigned char *)&n;
    return one_in_char[ptr[0]]+one_in_char[ptr[1]]+one_in_char[ptr[2]]+one_in_char[ptr[3]];
}
对任何数，任何体系结构的cpu， 只要 sizeof(int)-1 次加法。
而且很容易扩展到任何数据类型。
使用 case最慢， 使用条件转移要受流水线预测错误的干扰。

connet

在 P4 2.8G 上 redhat 9.0, 升级kernel 到2.4.32
不优化结果：
    time of func: 58   
    time of func2: 31   
O2优化结果：
    time of func: 22   
    time of func2: 17  

在 via C7 1.3G 上 kernel 2.6.16.22
不优化结果：
    time of func: 151   
    time of func2: 135   
O2优化结果：
    time of func: 25   
    time of func2: 40   


在 AMD64 3000+ 上， FC5, 2.6.16-1.2122_FC5
不优化结果：
    time of func: 48   
    time of func2: 61   
O2优化结果：
    time of func: 25   
    time of func2: 40   

在 AMD64 3000+ 上， redhat 9 2.4.20-8
不优化结果：
    time of func: 48   
    time of func2: 54   
O2优化结果：
    time of func: 24   
    time of func2: 41   

可以看到无论是否优化，在intel CPU 上， 我的算法快， 但是在 AMD+FC5 上，我的慢。
但是在 via C7上， 我的算法优化前快， 优化后反而比那个算法慢。
不优化 gcc -o one one.c
优化  gcc -O2 -o one2 one.c

程序如下：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

int count=0x7FFFFFFF;

unsigned int func(unsigned int x)
{
    x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL); // 0-2 in 2 bits
    x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL); // 0-4 in 4 bits
#if 1
    // Version 1
    x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL); // 0-8 in 8 bits
    x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL); // 0-16 in 16 bits
    x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL); // 0-31 in 32 bits
    return x;
#else
    // Version 2
    x = (x + (x >> 4)) & 0x0f0f0f0fUL; // 0-8 in 4 bits
    x += x >> 8; // 0-16 in 8 bits
    x += x >> 16; // 0-32 in 8 bits
    return x & 0xff;
#endif
}

int one_in_char[256];
int func2(int *v)
{
    unsigned char *ptr=(unsigned char *)v;
    return one_in_char[ptr[0]]+one_in_char[ptr[1]]+one_in_char[ptr[2]]+one_in_char[ptr[3]];
}

void test_1()
{
  int t1, t2;
  int i, v;
   char v2=0;
  t1 = time(NULL);
  for (i=0; i<count; i++)
    {
      v = func(i);
       v2+=v; /* 若不加这个，v 没使用,循环被优化掉了 */
    }
  t2 = time(NULL);
  printf("time of func: %d   v2=%d\n", t2-t1, v2);
}

void test_2()
{
  int t1, t2;
  int i, v;
   char v2=0;
  for (i=0; i<256; i++)
    one_in_char[i]=i%8;  /* 这 256 为硬编码， 为简便起见，随便设，不影响计算时间 */
  t1 = time(NULL);
  for (i=0; i<count; i++)
    {
      v = func2(&i);
       v2+=v; /* 若不加这个，v 没使用,循环被优化掉了 */
    }
  t2 = time(NULL);
  printf("time of func2: %d   v2=%d\n", t2-t1, v2);
}

int main(int argc, char **argv)
{
  test_1();
  test_2();
  return 0;
}

[[i] 本帖最后由 connet 于 2006-7-20 11:00 编辑 [/i]]

connet

原帖由 unicorns 于 2006-7-20 11:03 发表
http://bbs.chinaunix.net/viewthr ... p;extra=&page=1

一年多了.........

果然以前有人讨论过

connet

原帖由 liubinbj 于 2006-7-20 11:48 发表
楼主如果真是想挑战最快，那请用我的算法来对比吧，在我的《放出一个世界上最快的判断32位整数二进制中1的个数的算法》帖子里，楼主用于对比的方法已经被证明比我的算法慢，它不是最快的。

你怎么测试的呢？
我测试下来你的最慢。

connet

P4 2.8G redhat 9.0, kernel 2.4.32
不优化    liubinbj方法    网上方法     我的方法
              154.6641     63.7537    31.7395
O2优化    liubinbj方法   网上方法     我的方法
              78.1829       19.3305    13.0671

VIA C7 1.3G , 2.6.16.22
不优化    liubinbj方法   网上方法      我的方法
                431.7528   151.2660   169.5686
O2优化    liubinbj方法   网上方法     我的方法
                277.4617    58.1803    59.8410

AMD64 3000+  FC5, 2.6.16-1.2122_FC5
不优化    liubinbj方法   网上方法     我的方法
               180.3114    51.2969    62.6047
O2优化    liubinbj方法   网上方法     我的方法
               85.9299       21.0763    24.1614

任何平台下 liubinbj方法 最慢， 是其余方法的 3-5倍时间
欢迎挑战，欢迎测试
程序存为 one.c
不优化 gcc -o one one.c
优化  gcc -O2 -o one2 one.c
运行 one 和 one2 得到结果

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

unsigned int count=0x7FFFFFFF;


    static struct timeval _tstart, _tend;
    static struct timezone tz;

    void time_start(void)
    {
        gettimeofday(&_tstart, &tz);
    }
    void time_end(void)
    {
        gettimeofday(&_tend,&tz);
    }

    double time_val()
    {
        double t1, t2;

        t1 =  (double)_tstart.tv_sec + (double)_tstart.tv_usec/(1000*1000);
        t2 =  (double)_tend.tv_sec + (double)_tend.tv_usec/(1000*1000);
        return t2-t1;
    }
   
unsigned int func(unsigned int x)
{
    x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL); // 0-2 in 2 bits
    x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL); // 0-4 in 4 bits
#if 1
    // Version 1
    x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL); // 0-8 in 8 bits
    x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL); // 0-16 in 16 bits
    x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL); // 0-31 in 32 bits
    return x;
#else
    // Version 2
    x = (x + (x >> 4)) & 0x0f0f0f0fUL; // 0-8 in 4 bits
    x += x >> 8; // 0-16 in 8 bits
    x += x >> 16; // 0-32 in 8 bits
    return x & 0xff;
#endif
}

int one_in_char[256];
int func2(unsigned int  *v)
{
//    int n=v;
    unsigned char *ptr=(unsigned char *)v;
    return one_in_char[ptr[0]]+one_in_char[ptr[1]]+one_in_char[ptr[2]]+one_in_char[ptr[3]];
}

int func3(unsigned int n){
      
        int count=0;
        //高16位
        if(n&0xFFFF0000) {
                //高8
                if(n&0xFF000000) {
                        //高4
                        if(n&0xF0000000) {
                                if(n&0x10000000) count++;
                                if(n&0x20000000) count++;
                                if(n&0x40000000) count++;
                                if(n&0x80000000) count++;
                        }
                        //低4
                        if(n&0x0F000000) {
                                if(n&0x01000000) count++;
                                if(n&0x02000000) count++;
                                if(n&0x04000000) count++;
                                if(n&0x08000000) count++;
                        }                       
                }
                //低8
                if(n&0x00FF0000) {
                        //高4
                        if(n&0x00F00000) {
                                if(n&0x00100000) count++;
                                if(n&0x00200000) count++;
                                if(n&0x00400000) count++;
                                if(n&0x00800000) count++;
                        }
                        //低4
                        if(n&0x000F0000) {
                                if(n&0x00010000) count++;
                                if(n&0x00020000) count++;
                                if(n&0x00040000) count++;
                                if(n&0x00080000) count++;
                        }      
                }
        }
      
        //低16位
        if(n&0x0000FFFF) {
                //高8
                if(n&0x0000FF00) {
                        //高4
                        if(n&0x0000F000) {
                                if(n&0x00001000) count++;
                                if(n&0x00002000) count++;
                                if(n&0x00004000) count++;
                                if(n&0x00008000) count++;
                        }
                        //低4
                        if(n&0x00000F00) {
                                if(n&0x00000100) count++;
                                if(n&0x00000200) count++;
                                if(n&0x00000400) count++;
                                if(n&0x00000800) count++;
                        }      
                }
                //低8
                if(n&0x000000FF) {
                        //高4
                        if(n&0x000000F0) {
                                if(n&0x00000010) count++;
                                if(n&0x00000020) count++;
                                if(n&0x00000040) count++;
                                if(n&0x00000080) count++;
                        }
                        //低4
                        if(n&0x0000000F) {
                                if(n&0x00000001) count++;
                                if(n&0x00000002) count++;
                                if(n&0x00000004) count++;
                                if(n&0x00000008) count++;
                        }      
                }
        }

        return count;
}

void test_1()
{
  unsigned int i;
  char v, v2=0;
  time_start();
  for (i=0; i<count; i++)
    {
      v = func(i);
       v2+=v; /* 若不加这个，v 没使用,循环被优化掉了 */
    }
  time_end();
        printf("test func use %0.4f seconds, v2=%d\n",time_val(), v2);
}

void test_2()
{
  unsigned int i;
  char v, v2=0;
  for (i=0; i<256; i++)
    one_in_char[i]=i%8;  /* 这 256 为硬编码， 为简便起见，随便设，不影响计算时间 */
  time_start();
  for (i=0; i<count; i++)
    {
      v = func2(&i);
       v2+=v; /* 若不加这个，v 没使用,循环被优化掉了 */
    }
  time_end();
        printf("test func2 use %0.4f seconds, v2=%d\n",time_val(), v2);
}

void test_3()
{
  unsigned int i;
  char  v, v2=0;
  time_start();
  for (i=0; i<count; i++)
    {
      v = func3(i);
       v2+=v; /* 若不加这个，v 没使用,循环被优化掉了 */
    }
  time_end();
        printf("test func3 use %0.4f seconds, v2=%d\n",time_val(), v2);
}

int main(int argc, char **argv)
{
  test_1();
  test_2();
  test_3();
  return 0;
}

connet

原帖由 Arghawk 于 2006-7-20 13:56 发表
你这个方法跟http://bbs.chinaunix.net/viewthr ... p;extra=&page=1里面那个方法是一样的嘛，只是他算的是char中有多少个1，你算的是一个int中有多少个1

恩， 我看到了， 前面  unicorns  已经告诉我了。

你有更好的方法？

connet

[quote]原帖由 [i]liubinbj[/i] 于 2006-7-20 14:52 发表
to conect:
无论怎么算，首先应该正确。
你的代码速度倒是够快，可怎么总是返回0 ？我特别不解，不知道是不是我把你的函数理解错了？

我测试了看到的两个你的版本，测试代码如下：

[code]
int one_in_ch ... [/quote]
const int one_in_char[256]=
{
    0, 1, 1, 2, 1, 2,2,3
......
                              ,8
}
one_in_char 表示 0-255 这256 个数每个的1 的数目。我的测试程序只测试速度， 没有初始化这256个值。