如何计算32位整数中的设置位数？

Question

代表数字7的8位看起来像这样:

00000111

设置三位.

什么算法来确定32位整数中的设置位数？

Answer 1

这被称为' 汉明重量 ','popcount'或'侧向添加'.

"最佳"算法实际上取决于您使用的CPU以及您的使用模式.

一些CPU有一个内置指令来执行它,而另一些CPU具有作用于位向量的并行指令.并行指令(如x86 popcnt,在支持它的CPU上)几乎肯定会最快.一些其他架构可能具有使用微码环路实现的慢速指令,该循环每周期测试一点(需要引用).

如果您的CPU具有大缓存和/或您在紧密循环中执行大量这些指令,则预先填充的表查找方法可以非常快.然而,由于"高速缓存未命中"的代价,它可能会受到影响,其中CPU必须从主存储器中获取一些表.

如果你知道你的字节大部分是0或大部分是1,那么这些场景的算法非常有效.

我相信一个非常好的通用算法如下,称为"并行"或"可变精度SWAR算法".我用C语言伪语言表达了这一点,您可能需要调整它以适用于特定语言(例如,在C++中使用uint32_t,在Java中使用>>>):

int numberOfSetBits(int i)
{
     // Java: use >>> instead of >>
     // C or C++: use uint32_t
     i = i - ((i >> 1) & 0x55555555);
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
     return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

这具有所讨论的任何算法的最佳最坏情况行为,因此将有效地处理您抛出的任何使用模式或值.

这种按位SWAR算法可以在多个向量元素中同时进行并行化,而不是在单个整数寄存器中,以便在具有SIMD但没有可用的popcount指令的CPU上加速.(例如x86-64代码必须在任何CPU上运行,而不仅仅是Nehalem或更高版本.)

但是,对popcount使用向量指令的最佳方法通常是使用变量shuffle在每个字节并行执行4位的表查找.(4位索引保存在向量寄存器中的16个条目表).

在Intel CPU上,硬件64位popcnt指令可以胜过SSSE3 PSHUFB位并行实现大约2倍,但前提是你的编译器恰到好处.否则SSE可能会显着提前.较新的编译器版本了解Intel上的popcnt false依赖性 问题.

参考文献:

https://graphics.stanford.edu/~seander/bithacks.html

https://en.wikipedia.org/wiki/Hamming_weight

http://gurmeet.net/puzzles/fast-bit-counting-routines/

http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20(Ones%20Count)

Answer 2

还要考虑编译器的内置函数.

例如,在GNU编译器上,您可以使用:

int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);

在最坏的情况下,编译器将生成对函数的调用.在最好的情况下,编译器将发出cpu指令以更快地完成相同的工作.

GCC内在函数甚至可以跨多个平台工作.Popcount将成为x86架构的主流,因此现在开​​始使用内在函数是有意义的.其他架构多年来一直有很多人.

在x86上,您可以告诉编译器它可以假设支持popcnt指令,-mpopcnt或者-msse4.2也可以启用在同一代中添加的向量指令.请参阅GCC x86选项. -march=nehalem(或者-march=您希望代码承担和调整的任何CPU)都是一个不错的选择.在较旧的CPU上运行生成的二进制文件将导致非法指令错误.

要为构建它们的机器优化二进制文件,请使用-march=native (使用gcc,clang或ICC).

MSVC为x86 popcnt指令提供了内在功能,但与gcc不同,它实际上是硬件指令的固有内容,需要硬件支持.

使用std::bitset<>::count()而不是内置

理论上,任何知道如何有效地为目标CPU进行popcount的编译器都应该通过ISO C++公开该功能std::bitset<>.在实践中,对于某些目标CPU,在某些情况下,您可能会更好地使用bit-hack AND/shift/ADD.

对于硬件popcount是可选扩展(如x86)的目标体系结构,并非所有编译器都具有std::bitset在可用时利用它的优势.例如,MSVC无法popcnt在编译时启用支持,并且总是使用表查找,即使是/Ox /arch:AVX(这意味着SSE4.2,尽管从技术上讲,有一个单独的功能位popcnt.)

但至少你得到的东西在任何地方都可以使用,并且gcc/clang具有正确的目标选项,你可以获得支持它的架构的硬件popcount.

#include <bitset>
#include <limits>
#include <type_traits>

template<typename T>
//static inline  // static if you want to compile with -mpopcnt in one compilation unit but not others
typename std::enable_if<std::is_integral<T>::value,  unsigned >::type 
popcount(T x)
{
    static_assert(std::numeric_limits<T>::radix == 2, "non-binary type");

    // sizeof(x)*CHAR_BIT
    constexpr int bitwidth = std::numeric_limits<T>::digits + std::numeric_limits<T>::is_signed;
    // std::bitset constructor was only unsigned long before C++11.  Beware if porting to C++03
    static_assert(bitwidth <= std::numeric_limits<unsigned long long>::digits, "arg too wide for std::bitset() constructor");

    typedef typename std::make_unsigned<T>::type UT;        // probably not needed, bitset width chops after sign-extension

    std::bitset<bitwidth> bs( static_cast<UT>(x) );
    return bs.count();
}

在Godbolt编译器资源管理器中查看来自gcc,clang,icc和MSVC的asm.

x86-64 gcc -O3 -std=gnu++11 -mpopcnt发出以下信息:

unsigned test_short(short a) { return popcount(a); }
    movzx   eax, di      # note zero-extension, not sign-extension
    popcnt  rax, rax
    ret
unsigned test_int(int a) { return popcount(a); }
    mov     eax, edi
    popcnt  rax, rax
    ret
unsigned test_u64(unsigned long long a) { return popcount(a); }
    xor     eax, eax     # gcc avoids false dependencies for Intel CPUs
    popcnt  rax, rdi
    ret

PowerPC64 gcc -O3 -std=gnu++11发出(对于intarg版本):

    rldicl 3,3,0,32     # zero-extend from 32 to 64-bit
    popcntd 3,3         # popcount
    blr

这个源根本不是x86特定的或GNU特定的,但只能通过gcc/clang/icc很好地编译x86.

另请注意,gcc对没有单指令popcount的体系结构的回退是一次一个字节的表查找.例如,这对于ARM来说并不是很好.

Answer 3

在我看来,"最佳"解决方案是另一个程序员(或两年后的原始程序员)可以阅读而没有大量评论的解决方案.你可能想要一些已经提供的最快或最聪明的解决方案,但我更喜欢可读性而不是聪明.

unsigned int bitCount (unsigned int value) {
    unsigned int count = 0;
    while (value > 0) {           // until all bits are zero
        if ((value & 1) == 1)     // check lower bit
            count++;
        value >>= 1;              // shift bits, removing lower bit
    }
    return count;
}

如果你想要更快的速度(假设你记录好以帮助你的继任者),你可以使用表查找:

// Lookup table for fast calculation of bits set in 8-bit unsigned char.

static unsigned char oneBitsInUChar[] = {
//  0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F (<- n)
//  =====================================================
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, // 0n
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // 1n
    : : :
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, // Fn
};

// Function for fast calculation of bits set in 16-bit unsigned short.

unsigned char oneBitsInUShort (unsigned short x) {
    return oneBitsInUChar [x >>    8]
         + oneBitsInUChar [x &  0xff];
}

// Function for fast calculation of bits set in 32-bit unsigned int.

unsigned char oneBitsInUInt (unsigned int x) {
    return oneBitsInUShort (x >>     16)
         + oneBitsInUShort (x &  0xffff);
}

虽然这些依赖于特定的数据类型大小,因此它们不具备可移植性.但是,由于许多性能优化无论如何都不可移植,这可能不是问题.如果你想要便携性,我会坚持使用可读的解决方案.

Answer 4

来自Hacker's Delight,p.66,图5-2

int pop(unsigned x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

执行~20-ish指令(取决于arch),没有分支.

黑客的喜悦 是令人愉快的!强烈推荐.

Answer 5

我认为最快的方法 - 不使用查找表和popcount - 如下所示.只需12次操作即可对设定位进行计数.

int popcount(int v) {
    v = v - ((v >> 1) & 0x55555555);                // put count of each 2 bits into those 2 bits
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits  
    return c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

这是有效的,因为您可以通过分成两半来计算设置位的总数,计算两半中的设置位数,然后将它们相加.也被称为Divide and Conquer范式.让我们详细介绍..

v = v - ((v >> 1) & 0x55555555); 

两位中的位数可以是0b00,0b01或0b10.让我们试着用2位来解决这个问题.

 ---------------------------------------------
 |   v    |   (v >> 1) & 0b0101   |  v - x   |
 ---------------------------------------------
   0b00           0b00               0b00   
   0b01           0b00               0b01     
   0b10           0b01               0b01
   0b11           0b01               0b10

这是所需要的:最后一列显示每两位对中的设置位数.如果>= 2 (0b10)然后and产生两位数0b01,则产生0b00.

v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 

这个陈述应该很容易理解.在第一次操作之后,我们每两位有一个设置位的计数,现在我们总计每4位的计数.

v & 0b00110011         //masks out even two bits
(v >> 2) & 0b00110011  // masks out odd two bits

然后我们总结上面的结果,给出4位的设置位总数.最后的陈述是最棘手的.

c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

让我们进一步分解......

v + (v >> 4)

它类似于第二个陈述; 我们正在计算4个组中的设置位.我们知道 - 因为我们以前的操作 - 每个半字节都有其中的设置位数.让我们看一个例子.假设我们有字节0b01000010.这意味着第一个半字节设置了4比特,第二个设置了2比特.现在我们将这些小块一起添加.

0b01000010 + 0b01000000

它给出了第一个半字节中字节中设置位的计数,0b01100010因此我们屏蔽了数字中所有字节的最后四个字节(丢弃它们).

0b01100010 & 0xF0 = 0b01100000

现在每个字节都有其中的设置位数.我们需要将它们全部加在一起.诀窍是将结果乘以0b10101010有趣的属性.如果我们的数字有四个字节,A B C D它将产生一个带有这些字节的新数字A+B+C+D B+C+D C+D D.一个4字节的数字最多可以设置32位,可以表示为0b00100000.

我们现在需要的是第一个字节,它具有所有字节中所有设置位的总和,我们得到它 >> 24.该算法是为32 bit单词设计的,但可以很容易地修改为64 bit单词.

Answer 6

如果您碰巧使用Java,则内置方法Integer.bitCount将执行此操作.

Answer 7

我感到无聊,并计划了三次迭代的三种方法.编译器是gcc -O3.CPU是他们放在第一代Macbook Pro中的任何东西.

最快的是以下,在3.7秒:

static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount( unsigned int i )
{
    return( wordbits[i&0xFFFF] + wordbits[i>>16] );
}

第二位是相同的代码,但查找4个字节而不是2个半字.这需要大约5.5秒.

排在第三位的是"斜向加法",耗时8.6秒.

排在第四位的是GCC的__builtin_popcount(),这是一个可耻的11秒.

一次一位计数的方法慢得多,我厌倦了等待它完成.

因此,如果您关注性能高于其他所有,那么请使用第一种方法.如果您在意,但还不足以花费64Kb的RAM,请使用第二种方法.否则使用可读(但缓慢)的一次一位方法.

很难想象你想要使用比特笨拙的方法的情况.

编辑:这里的结果相似.

Answer 8

unsigned int count_bit(unsigned int x)
{
  x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
  x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
  x = (x & 0x0000FFFF) + ((x >> 16)& 0x0000FFFF);
  return x;
}

让我解释一下这个算法.

该算法基于Divide and Conquer算法.假设有一个8位整数213(二进制11010101),算法就像这样(每次合并两个相邻块):

+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |  <- x
|  1 0  |  0 1  |  0 1  |  0 1  |  <- first time merge
|    0 0 1 1    |    0 0 1 0    |  <- second time merge
|        0 0 0 0 0 1 0 1        |  <- third time ( answer = 00000101 = 5)
+-------------------------------+

Answer 9

这是有助于了解您的微架构的问题之一.我只是使用C++内联在gcc 4.3.3下使用-O3编译了两个变体来消除函数调用开销,十亿次迭代,保持所有计数的运行总和以确保编译器不会删除任何重要的东西,使用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;
}

未经修改的Hacker's Delight花了12.2万亿美元.我的并行版本(计数两倍的位数)运行在13.0 gigacycles中.在2.4GHz Core Duo上共同使用了10.5秒.25个gigacycles =在这个时钟频率下超过10秒,所以我有信心我的时间是正确的.

这与指令依赖链有关,这对于该算法非常不利.通过使用一对64位寄存器,我几乎可以将速度提高一倍.事实上,如果我很聪明并且加上x + ya,我可以更快地削减一些变化.带有一些小调整的64位版本会出现关于偶数,但再次计算两倍的位数.

使用128位SIMD寄存器,另外两个因子,SSE指令集通常也有巧妙的快捷方式.

代码没有理由特别透明.界面简单,算法可以在很多地方在线参考,并且可以进行全面的单元测试.偶然发现它的程序员甚至可能会学到一些东西.这些位操作在机器级别非常自然.

好吧,我决定对经过调整的64位版本进行测试.对于这个sizeof(无符号长)== 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位寄存器略好.

让我们看看这里是否有更多的流水线操作.这涉及更多,所以我实际测试了一下.每个术语单独总计为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播放内联技巧,即使我在某些测试中没有使用inline关键字.当我让gcc玩弄技巧时,十亿次调用pop4()需要12.56个gigatcles,但我确定它是将参数折叠为常量表达式.一个更现实的数字似乎是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(); 

在8.17s中总计了2560亿比特.在16位表查找中作为基准测试,以3200万位的速度运行到1.02s.无法直接比较,因为另一个工作台没有给出时钟速度,但看起来我已经把64位表版本中的鼻涕打了出来,这首先是对L1缓存的悲剧性使用.

更新:决定做明显的事情,并通过添加四个重复的行来创建pop6().得出22.8gc,经过9.5s总计3840亿比特.所以还有另外20%现在800毫秒,320亿比特.

Answer 10

为什么不迭代地除以2？

count = 0
while n > 0
  if (n % 2) == 1
    count += 1
  n /= 2  

我同意这不是最快的,但"最好的"有点含糊不清.我认为"最好的"应该有一个清晰的元素

Answer 11

当你写出位模式时,Hacker's Delight bit-twiddling变得更加清晰.

unsigned int bitCount(unsigned int x)
{
  x = ((x >> 1) & 0b01010101010101010101010101010101)
     + (x       & 0b01010101010101010101010101010101);
  x = ((x >> 2) & 0b00110011001100110011001100110011)
     + (x       & 0b00110011001100110011001100110011); 
  x = ((x >> 4) & 0b00001111000011110000111100001111)
     + (x       & 0b00001111000011110000111100001111); 
  x = ((x >> 8) & 0b00000000111111110000000011111111)
     + (x       & 0b00000000111111110000000011111111); 
  x = ((x >> 16)& 0b00000000000000001111111111111111)
     + (x       & 0b00000000000000001111111111111111); 
  return x;
}

第一步将偶数位加到奇数位,产生每两位的位数.其他步骤将高阶块添加到低阶块,将块大小加倍,直到我们将最终计数占用整个int.

Answer 12

对于2 ³²查找表和单独迭代每个位之间的愉快介质:

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

Answer 13

这可以在O(k),k设置的位数在哪里完成.

int NumberOfSetBits(int n)
{
    int count = 0;

    while (n){
        ++ count;
        n = (n - 1) & n;
    }

    return count;
}

Answer 14

这不是最快或最好的解决方案,但我找到了同样的问题,我开始思考和思考.最后我意识到,如果从数学方面得到问题并绘制图形,然后你会发现它是一个具有某些周期性部分的函数,然后你意识到周期之间的差异......就这样可以这样做.干得好:

unsigned int f(unsigned int x)
{
    switch (x) {
        case 0:
            return 0;
        case 1:
            return 1;
        case 2:
            return 1;
        case 3:
            return 2;
        default:
            return f(x/4) + f(x%4);
    }
}

Answer 15

您正在寻找的功能通常称为二进制数的"横向总和"或"人口数".Knuth在前分册1A,pp11-12中对此进行了讨论(尽管在第2卷,4.6.3-(7)中有一个简短的参考文献.)

该轨迹classicus是彼得·韦格纳的文章"一种用于在二进制电脑计数问鼎技术",从ACM通信,第3卷(1960)5号,322页.他在那里给出了两种不同的算法,一种针对期望为"稀疏"的数量进行优化(即,具有少量的数字),并针对相反的情况进行优化.

Answer 16

几个未解决的问题: -

1. 如果数字是负数那么？
2. 如果数字是1024,则"迭代除以2"方法将迭代10次.

我们可以修改算法以支持负数如下: -

count = 0
while n != 0
if ((n % 2) == 1 || (n % 2) == -1
    count += 1
  n /= 2  
return count

现在要克服第二个问题,我们可以像算法一样写: -

int bit_count(int num)
{
    int count=0;
    while(num)
    {
        num=(num)&(num-1);
        count++;
    }
    return count;
}

完整参考请参阅:

http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html

Answer 17

  private int get_bits_set(int v)
    {
      int c; // c accumulates the total bits set in v
        for (c = 0; v>0; c++)
        {
            v &= v - 1; // clear the least significant bit set
        }
        return c;
    }

Answer 18

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

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

逻辑:n&(n-1)复位n的最后一位.

PS:我知道这不是O(1)解决方案,尽管这是一个有趣的解决方案.

Answer 19

我认为Brian Kernighan的方法也很有用......它经历了与设置位一样多的迭代.因此,如果我们有一个只有高位设置的32位字,那么它只会循环一次.

int countSetBits(unsigned int n) { 
    unsigned int n; // count the number of bits set in n
    unsigned int c; // c accumulates the total bits set in n
    for (c=0;n>0;n=n&(n-1)) c++; 
    return c; 
}

1988年出版,C编程语言第2版.(Brian W. Kernighan和Dennis M. Ritchie)在练习2-9中提到了这一点.2006年4月19日,Don Knuth向我指出,这种方法"首先由Peter Wegner在CACM 3(1960),322中发表."(也由Derrick Lehmer独立发现并于1964年在Beckenbach编辑的一本书中出版.)

Answer 20

"最佳算法"是什么意思？短代码或禁食代码？您的代码看起来非常优雅,并且具有恒定的执行时间.代码也很短.

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

       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位值可能更快.

Answer 21

我在1990年左右为RISC机器编写了一个快速的bitcount宏.它不使用高级算术(乘法,除法,%),内存提取(方式太慢),分支(方式太慢),但它确实假设CPU有一个32位桶形移位器(换句话说,>> 1和>> 32采用相同的周期数.)它假设小的常数(例如6,12,24)无需加载到寄存器中,或者存储在临时工中,一遍又一遍地重复使用.

根据这些假设,在大多数RISC机器上,它在大约16个周期/指令中计数32位.请注意,15个指令/周期接近循环或指令数的下限,因为它似乎需要至少3个指令(掩码,移位,运算符)才能将加数减少一半,因此log_2(32) = 5,5 x 3 = 15条指令是准下限.

#define BitCount(X,Y)           \
                Y = X - ((X >> 1) & 033333333333) - ((X >> 2) & 011111111111); \
                Y = ((Y + (Y >> 3)) & 030707070707); \
                Y =  (Y + (Y >> 6)); \
                Y = (Y + (Y >> 12) + (Y >> 24)) & 077;

这是第一个也是最复杂步骤的秘密:

input output
AB    CD             Note
00    00             = AB
01    01             = AB
10    01             = AB - (A >> 1) & 0x1
11    10             = AB - (A >> 1) & 0x1

所以如果我取上面的第1列(A),将它向右移1位,然后从AB中减去它,得到输出(CD).3位的扩展是类似的; 如果你愿意,你可以用我上面的8行布尔表来检查它.

• 唐吉利斯

Answer 22

如果你正在使用C++,另一种选择是使用模板元编程:

// recursive template to sum bits in an int
template <int BITS>
int countBits(int val) {
        // return the least significant bit plus the result of calling ourselves with
        // .. the shifted value
        return (val & 0x1) + countBits<BITS-1>(val >> 1);
}

// template specialisation to terminate the recursion when there's only one bit left
template<>
int countBits<1>(int val) {
        return val & 0x1;
}

用法是:

// to count bits in a byte/char (this returns 8)
countBits<8>( 255 )

// another byte (this returns 7)
countBits<8>( 254 )

// counting bits in a word/short (this returns 1)
countBits<16>( 256 )

您当然可以进一步扩展此模板以使用不同类型(甚至自动检测位大小),但为了清晰起见,我保持简单.

编辑:忘了提到这很好,因为它应该可以在任何C++编译器中工作,它基本上只是为你计算循环,如果一个常数值用于位数(换句话说,我很确定它是最快的通用方法你会找到)

Answer 23

你能做的是

while(n){
    n=n&(n-1);
    count++;
}

这背后的逻辑是 n-1 的位从 n 的最右边的设置位反转。如果 n=6 即 110 那么 5 是 101 这些位从 n 的最右边设置位反转。所以如果我们 & 这两个我们将在每次迭代中使最右边的位为 0，并且总是转到下一个最右边的设置位。因此，计算设置位。当每个位都设置时，最坏的时间复杂度将是 O(logn)。

Answer 24

我特别喜欢财富文件中的这个例子:

#define BITCOUNT(x)    (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x)         ((x) - (((x)>>1)&0x77777777)
                             - (((x)>>2)&0x33333333)
                             - (((x)>>3)&0x11111111))

我最喜欢它因为它太漂亮了!

Answer 25

Java JDK1.5

Integer.bitCount(N);

其中n是要计算1的数字.

检查一下,

Integer.highestOneBit(n);
Integer.lowestOneBit(n);
Integer.numberOfLeadingZeros(n);
Integer.numberOfTrailingZeros(n);

//Beginning with the value 1, rotate left 16 times
     n = 1;
         for (int i = 0; i < 16; i++) {
            n = Integer.rotateLeft(n, 1);
            System.out.println(n);
         }

Answer 26

我在使用SIMD指令(SSSE3和AVX2)的阵列中找到了位计数的实现.它的性能比使用__popcnt64内部函数要好2-2.5倍.

SSSE3版本:

#include <smmintrin.h>
#include <stdint.h>

const __m128i Z = _mm_set1_epi8(0x0);
const __m128i F = _mm_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m128i T = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);

uint64_t BitCount(const uint8_t * src, size_t size)
{
    __m128i _sum =  _mm128_setzero_si128();
    for (size_t i = 0; i < size; i += 16)
    {
        //load 16-byte vector
        __m128i _src = _mm_loadu_si128((__m128i*)(src + i));
        //get low 4 bit for every byte in vector
        __m128i lo = _mm_and_si128(_src, F);
        //sum precalculated value from T
        _sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, lo)));
        //get high 4 bit for every byte in vector
        __m128i hi = _mm_and_si128(_mm_srli_epi16(_src, 4), F);
        //sum precalculated value from T
        _sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, hi)));
    }
    uint64_t sum[2];
    _mm_storeu_si128((__m128i*)sum, _sum);
    return sum[0] + sum[1];
}

AVX2版本:

#include <immintrin.h>
#include <stdint.h>

const __m256i Z = _mm256_set1_epi8(0x0);
const __m256i F = _mm256_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m256i T = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
                                   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);

uint64_t BitCount(const uint8_t * src, size_t size)
{
    __m256i _sum =  _mm256_setzero_si256();
    for (size_t i = 0; i < size; i += 32)
    {
        //load 32-byte vector
        __m256i _src = _mm256_loadu_si256((__m256i*)(src + i));
        //get low 4 bit for every byte in vector
        __m256i lo = _mm256_and_si256(_src, F);
        //sum precalculated value from T
        _sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, lo)));
        //get high 4 bit for every byte in vector
        __m256i hi = _mm256_and_si256(_mm256_srli_epi16(_src, 4), F);
        //sum precalculated value from T
        _sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, hi)));
    }
    uint64_t sum[4];
    _mm256_storeu_si256((__m256i*)sum, _sum);
    return sum[0] + sum[1] + sum[2] + sum[3];
}

Answer 27

我总是在竞争性编程中使用它,它易于编写和高效:

#include <bits/stdc++.h>

using namespace std;

int countOnes(int n) {
    bitset<32> b(n);
    return b.count();
}

Answer 28

C++20 std::popcount

以下提案已合并http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html并应将其添加到<bit>标题中。

我希望用法如下：

#include <bit>
#include <iostream>

int main() {
    std::cout << std::popcount(0x55) << std::endl;
}

当支持到达 GCC 时，我会尝试一下，GCC 9.1.0g++-9 -std=c++2a仍然不支持它。

提案说：

标题： <bit>

namespace std {

  // 25.5.6, counting
  template<class T>
    constexpr int popcount(T x) noexcept;

和：

template<class T>
  constexpr int popcount(T x) noexcept;

约束：T 是无符号整数类型（3.9.1 [basic.fundamental]）。

返回： x 值中 1 的位数。

std::rotl并且std::rotr还添加了循环位旋转：Best practice for circle shift (rotate) operations in C++

Answer 29

这是一个便携式模块(ANSI-C),可以在任何架构上对每个算法进行基准测试.

你的CPU有9位字节？没问题:-)目前它实现了2种算法,K&R算法和字节明智的查找表.查找表平均比K&R算法快3倍.如果有人可以想办法让"Hacker's Delight"算法便于携带,请随意添加.

#ifndef _BITCOUNT_H_
#define _BITCOUNT_H_

/* Return the Hamming Wieght of val, i.e. the number of 'on' bits. */
int bitcount( unsigned int );

/* List of available bitcount algorithms.  
 * onTheFly:    Calculate the bitcount on demand.
 *
 * lookupTalbe: Uses a small lookup table to determine the bitcount.  This
 * method is on average 3 times as fast as onTheFly, but incurs a small
 * upfront cost to initialize the lookup table on the first call.
 *
 * strategyCount is just a placeholder. 
 */
enum strategy { onTheFly, lookupTable, strategyCount };

/* String represenations of the algorithm names */
extern const char *strategyNames[];

/* Choose which bitcount algorithm to use. */
void setStrategy( enum strategy );

#endif

.

#include <limits.h>

#include "bitcount.h"

/* The number of entries needed in the table is equal to the number of unique
 * values a char can represent which is always UCHAR_MAX + 1*/
static unsigned char _bitCountTable[UCHAR_MAX + 1];
static unsigned int _lookupTableInitialized = 0;

static int _defaultBitCount( unsigned int val ) {
    int count;

    /* Starting with:
     * 1100 - 1 == 1011,  1100 & 1011 == 1000
     * 1000 - 1 == 0111,  1000 & 0111 == 0000
     */
    for ( count = 0; val; ++count )
        val &= val - 1;

    return count;
}

/* Looks up each byte of the integer in a lookup table.
 *
 * The first time the function is called it initializes the lookup table.
 */
static int _tableBitCount( unsigned int val ) {
    int bCount = 0;

    if ( !_lookupTableInitialized ) {
        unsigned int i;
        for ( i = 0; i != UCHAR_MAX + 1; ++i )
            _bitCountTable[i] =
                ( unsigned char )_defaultBitCount( i );

        _lookupTableInitialized = 1;
    }

    for ( ; val; val >>= CHAR_BIT )
        bCount += _bitCountTable[val & UCHAR_MAX];

    return bCount;
}

static int ( *_bitcount ) ( unsigned int ) = _defaultBitCount;

const char *strategyNames[] = { "onTheFly", "lookupTable" };

void setStrategy( enum strategy s ) {
    switch ( s ) {
    case onTheFly:
        _bitcount = _defaultBitCount;
        break;
    case lookupTable:
        _bitcount = _tableBitCount;
        break;
    case strategyCount:
        break;
    }
}

/* Just a forwarding function which will call whichever version of the
 * algorithm has been selected by the client 
 */
int bitcount( unsigned int val ) {
    return _bitcount( val );
}

#ifdef _BITCOUNT_EXE_

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

/* Use the same sequence of pseudo random numbers to benmark each Hamming
 * Weight algorithm.
 */
void benchmark( int reps ) {
    clock_t start, stop;
    int i, j;
    static const int iterations = 1000000;

    for ( j = 0; j != strategyCount; ++j ) {
        setStrategy( j );

        srand( 257 );

        start = clock(  );

        for ( i = 0; i != reps * iterations; ++i )
            bitcount( rand(  ) );

        stop = clock(  );

        printf
            ( "\n\t%d psudoe-random integers using %s: %f seconds\n\n",
              reps * iterations, strategyNames[j],
              ( double )( stop - start ) / CLOCKS_PER_SEC );
    }
}

int main( void ) {
    int option;

    while ( 1 ) {
        printf( "Menu Options\n"
            "\t1.\tPrint the Hamming Weight of an Integer\n"
            "\t2.\tBenchmark Hamming Weight implementations\n"
            "\t3.\tExit ( or cntl-d )\n\n\t" );

        if ( scanf( "%d", &option ) == EOF )
            break;

        switch ( option ) {
        case 1:
            printf( "Please enter the integer: " );
            if ( scanf( "%d", &option ) != EOF )
                printf
                    ( "The Hamming Weight of %d ( 0x%X ) is %d\n\n",
                      option, option, bitcount( option ) );
            break;
        case 2:
            printf
                ( "Please select number of reps ( in millions ): " );
            if ( scanf( "%d", &option ) != EOF )
                benchmark( option );
            break;
        case 3:
            goto EXIT;
            break;
        default:
            printf( "Invalid option\n" );
        }

    }

 EXIT:
    printf( "\n" );

    return 0;
}

#endif

Answer 30

有许多算法来计算设定位; 但我认为最好的一个是更快的!您可以在此页面上看到详细信息:

比特扭曲黑客

我建议这个:

使用64位指令对以24,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.

Answer 31

快速C#解决方案使用预先计算的字节位计数表,并在输入大小上进行分支.

public static class BitCount
{
    public static uint GetSetBitsCount(uint n)
    {
        var counts = BYTE_BIT_COUNTS;
        return n <= 0xff ? counts[n]
             : n <= 0xffff ? counts[n & 0xff] + counts[n >> 8]
             : n <= 0xffffff ? counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff]
             : counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff] + counts[(n >> 24) & 0xff];
    }

    public static readonly uint[] BYTE_BIT_COUNTS = 
    {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
    };
}