"最佳算法"是什么意思?短码还是长码?您的代码看起来非常优雅，并且具有恒定的执行时间。代码也很短。

但如果速度是主要因素，而不是代码大小，那么我认为以下方法可以更快:

       static final int[] BIT_COUNT = { 0, 1, 1, ... 256 values with a bitsize of a byte ... };
        static int bitCountOfByte( int value ){
            return BIT_COUNT[ value & 0xFF ];
        }

        static int bitCountOfInt( int value ){
            return bitCountOfByte( value ) 
                 + bitCountOfByte( value >> 8 ) 
                 + bitCountOfByte( value >> 16 ) 
                 + bitCountOfByte( value >> 24 );
        }

我认为这不会更快的64位值，但32位值可以更快。

我个人使用这个:

  public static int myBitCount(long L){
      int count = 0;
      while (L != 0) {
         count++;
         L ^= L & -L; 
      }
      return count;
  }

有许多算法来计数设置位;但是我认为最好的一个是更快的一个! 您可以在本页查看详细信息:

Bit Twiddling Hacks

我建议这样做:

使用64位指令计数在14,24或32位字中设置的位

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v

// option 1, for at most 14-bit values in v:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;

// option 2, for at most 24-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) 
     % 0x1f;

// option 3, for at most 32-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 
     0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

这种方法需要64位CPU和快速模除法来提高效率。第一个选项只需要3个操作;第二种选择需要10;第三种选择需要15分钟。

对于232查找表和逐个遍历每个位之间的折中方法:

int bitcount(unsigned int num){
    int count = 0;
    static int nibblebits[] =
        {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
    for(; num != 0; num >>= 4)
        count += nibblebits[num & 0x0f];
    return count;
}

从http://ctips.pbwiki.com/CountBits

我使用下面更直观的代码。

int countSetBits(int n) {
    return !n ? 0 : 1 + countSetBits(n & (n-1));
}

逻辑:n & (n-1)重置n的最后一个集合位。

附注:我知道这不是O(1)解，尽管这是一个有趣的解。

这是一个有助于了解您的微架构的问题。我只是在gcc 4.3.3下用-O3编译的两个变量使用c++内联来计时，以消除函数调用开销，十亿次迭代，保持所有计数的运行总和，以确保编译器不删除任何重要的东西，使用rdtsc计时(精确的时钟周期)。

inline int pop2(unsigned x, unsigned y)
{
    x = x - ((x >> 1) & 0x55555555);
    y = y - ((y >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    y = (y & 0x33333333) + ((y >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    y = (y + (y >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    y = y + (y >> 8);
    x = x + (x >> 16);
    y = y + (y >> 16);
    return (x+y) & 0x000000FF;
}

未经修改的黑客喜悦需要122亿周期。我的并行版本(计算的比特数是它的两倍)的运行周期为13.0千兆周期。在2.4GHz的酷睿双核上，两者总共消耗了10.5秒。在这个时钟频率下，25千兆周期= 10秒多一点，所以我相信我的计时是正确的。

这与指令依赖链有关，这对算法非常不利。通过使用一对64位寄存器，我几乎可以再次将速度提高一倍。事实上，如果我聪明一点，早点加上x+y，我就可以减少一些移位。64位版本做了一些小的调整，结果是相同的，但又增加了一倍的比特数。

对于128位SIMD寄存器，这是另一个因素，SSE指令集通常也有聪明的快捷方式。

没有理由让代码特别透明。该算法界面简单，可在多处在线引用，并能通过全面的单元测试。偶然发现它的程序员甚至可能学到一些东西。这些位操作在机器级别上是非常自然的。

好吧，我决定搁置调整后的64位版本。对于这个sizeof(unsigned long) == 8

inline int pop2(unsigned long x, unsigned long y)
{
    x = x - ((x >> 1) & 0x5555555555555555);
    y = y - ((y >> 1) & 0x5555555555555555);
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
    y = (y & 0x3333333333333333) + ((y >> 2) & 0x3333333333333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
    y = (y + (y >> 4)) & 0x0F0F0F0F0F0F0F0F;
    x = x + y; 
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x + (x >> 32); 
    return x & 0xFF;
}

这看起来是对的(不过我没有仔细测试)。现在计时结果是10.70亿周期/ 14.1亿周期。后面的数字加起来是1280亿比特，相当于这台机器运行了5.9秒。非并行版本稍微加快了一点，因为我在64位模式下运行，它更喜欢64位寄存器，而不是32位寄存器。

让我们看看这里是否有更多的OOO管道。这有点复杂，所以我实际上测试了一些。每一项单独加起来是64，所有项加起来是256。

inline int pop4(unsigned long x, unsigned long y, 
                unsigned long u, unsigned long v)
{
  enum { m1 = 0x5555555555555555, 
         m2 = 0x3333333333333333, 
         m3 = 0x0F0F0F0F0F0F0F0F, 
         m4 = 0x000000FF000000FF };

    x = x - ((x >> 1) & m1);
    y = y - ((y >> 1) & m1);
    u = u - ((u >> 1) & m1);
    v = v - ((v >> 1) & m1);
    x = (x & m2) + ((x >> 2) & m2);
    y = (y & m2) + ((y >> 2) & m2);
    u = (u & m2) + ((u >> 2) & m2);
    v = (v & m2) + ((v >> 2) & m2);
    x = x + y; 
    u = u + v; 
    x = (x & m3) + ((x >> 4) & m3);
    u = (u & m3) + ((u >> 4) & m3);
    x = x + u; 
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x & m4; 
    x = x + (x >> 32);
    return x & 0x000001FF;
}

我兴奋了一会儿，但结果是gcc在-O3上玩内联的把戏，尽管我在一些测试中没有使用内联关键字。当我让gcc玩把戏时，对pop4()的十亿次调用需要12.56 gigacycles，但我确定它是将参数折叠为常量表达式。更实际的数字似乎是19.6gc，以实现30%的加速。我的测试循环现在看起来像这样，确保每个参数足够不同，以阻止gcc耍花招。

   hitime b4 = rdtsc(); 
   for (unsigned long i = 10L * 1000*1000*1000; i < 11L * 1000*1000*1000; ++i) 
      sum += pop4 (i,  i^1, ~i, i|1); 
   hitime e4 = rdtsc(); 

2560亿比特加起来在8.17秒内过去了。根据16位表查找的基准测试，3200万比特的计算结果为1.02秒。不能直接比较，因为另一个工作台没有给出时钟速度，但看起来我已经把64KB表版本的鼻涕打出来了，这首先是L1缓存的悲惨使用。

更新:决定做明显的和创建pop6()通过增加四个重复的行。结果是22.8gc, 3840亿比特在9.5秒内加起来。所以还有20%现在是800毫秒，320亿比特。