如何计算32位整数中的设置位数？
代表数字7的8位看起来像这样：
00000111
设置了三个位。
确定32位整数中的置位位数的算法是什么？
解决方案
这就是所谓的"锤子重量"，"弹出计数"或者"侧身加法"。
"最佳"算法实际上取决于我们所使用的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的最佳方法通常是使用可变混洗在每个字节并行的时间一次对4位进行表查找。 (这4位索引了保存在向量寄存器中的16个条目表)。
在Intel CPU上，硬件64位popcnt指令的性能可以比SSSE3PSHUFB位并行实现高2倍左右，但前提是编译器正确地执行了该指令。否则，上证所可能会明显领先。较新的编译器版本知道Intel上的popcnt错误依赖项问题。
参考：
https://graphics.stanford.edu/~seander/bithacks.html
https://zh.wikipedia.org/wiki/汉明重量
http://gurmeet.net/puzzles/fast-bit-counting-routines/
http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20(Ones%20Count)
为什么不迭代除以2？
count = 0
while n > 0
if (n % 2) == 1
count += 1
n /= 2
我同意这不是最快的方法，但是"最佳"方法有些含糊。我认为，"最佳"应该具有明确性
如果我们恰巧使用Java，则内置方法Integer.bitCount将执行此操作。
还请考虑编译器的内置函数。
例如，在GNU编译器上，我们可以使用：
int __builtin_popcount (unsigned int x); int __builtin_popcountll (unsigned long long x);
在最坏的情况下，编译器将生成对函数的调用。在最佳情况下，编译器将发出一条cpu指令以更快地完成相同的工作。
GCC内部函数甚至可以跨多个平台工作。 Popcount将成为x86架构中的主流，因此现在就开始使用内在函数是有意义的。其他架构的流行人数已经很多年了。
在x86上，我们可以告诉编译器它可以通过-mpopcnt或者-msse4.2来支持对popcnt指令的支持，从而也可以启用在同一代中添加的矢量指令。请参阅GCC x86选项。 -march = nehalem(或者-march =我们希望代码采用并对其进行调整的任何CPU)都是不错的选择。在较旧的CPU上运行生成的二进制文件将导致非法指令错误。
为了使二进制文件针对我们在其上构建的计算机进行优化，请使用-march = native(与gcc，clang或者ICC一起使用)。
MSVC提供了x86popcnt指令的内在函数，但与gcc不同，它实际上是硬件指令的内在函数，需要硬件支持。
使用std :: bitset <> :: count()而不是内置的
从理论上讲，任何知道如何为目标CPU有效地增加计数的编译器都应通过ISO C ++std :: bitset <>公开该功能。实际上，对于某些目标CPU，在某些情况下使用位破解AND / shift / ADD可能会更好。
对于硬件popcount是可选扩展(例如x86)的目标体系结构，并不是所有的编译器都具有一个可用的std :: bitset来利用它。例如，MSVC无法在编译时启用popcnt支持，并且始终使用表查找，即使使用/ Ox / arch：AVX(这意味着SSE4.2，尽管从技术上讲，它还有一个单独的功能位) popcnt。)
但是，至少我们可以获得随处可见的便携式产品，并且使用带有正确目标选项的gcc / clang，我们可以获得支持它的体系结构的硬件弹出数量。
#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-64gcc -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
发出PowerPC64gcc -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来说不是很好。
"最佳算法"是什么意思？短代码还是禁食代码？代码看起来非常优雅，并且执行时间恒定。代码也很短。
但是，如果速度是主要因素，而不是代码大小，那么我认为可以更快一些：
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位值，它会更快。
摘自《骇客的喜悦》，第6页。 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位数的指令(取决于拱形)执行，无分支。
黑客的喜悦是令人愉快的！强烈推荐。
我认为，"最佳"解决方案是可以由另一位程序员(或者两年后的原始程序员)阅读而无需大量评论的解决方案。我们可能想要某些已经提供的最快或者最聪明的解决方案，但我随时都希望可读性胜于聪明。
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);
}
尽管这些依赖于特定的数据类型大小，所以它们不那么可移植。但是，由于许多性能优化都不是可移植的，因此这可能不是问题。如果我们想要便携性，我会坚持使用可读的解决方案。
对于在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
我特别喜欢财富文件中的这个示例：
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x) ((x) - (((x)>>1)&0x77777777)
- (((x)>>2)&0x33333333)
- (((x)>>3)&0x11111111))
我最喜欢它，因为它是如此漂亮！
我们要查找的函数通常称为二进制数的"横向和"或者"人口数"。 Knuth在Fascicle 1A之前的pp11-12中对此进行了讨论(尽管在第2卷4.6.3-(7)中有简短的参考资料)。
经典所在地是彼得·韦格纳(Peter Wegner)的文章"一种在二进制计算机中计数的技术"，摘自ACM通讯，第3卷(1960)，第5页，第322页。他给出了两种不同的算法，其中一种针对预期的数字进行了优化。是"稀疏的"(即数量很少)，而对于相反的情况则是"稀疏"。
我很无聊，并为三种方法的十亿次迭代定了时间。编译器是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，请使用第二种方法。否则，请使用可读的(但速度较慢)一次一位的方法。
很难想到我们想使用位旋转方法的情况。
编辑：这里类似的结果。
这是有助于我们了解微体系结构的问题之一。我刚刚在使用-O3的gcc 4.3.3下使用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;
}
未经修改的Hacker's Delight花费了12.2 gigacycles。我的并行版本(计数为两倍)在13.0千兆周期内运行。两者在2.4GHz Core Duo上的总耗时为10.5s。 25 gigacycles =刚好超过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吉比特。后面的数字总计1,280亿位，相当于该计算机上经过的5.9s。非并行版本的速度有所提高，因为我以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;
}
我激动了片刻，但事实证明，即使我在某些测试中未使用inline关键字，gcc也在使用-O3进行内联技巧。当我让gcc发挥作用时，十亿次调用pop4()花费了12.56个千兆字节，但我确定它是将参数折叠为常量表达式。一个更现实的数字似乎是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内总计有2,560亿个比特流逝按照16位表查找中的基准，可以为3200万位计算出1.02s的时间。无法直接进行比较，因为另一个工作台没有提供时钟速度，但是好像我已经在64KB表版本中打了个鼻涕，这首先是对L1缓存的悲剧性使用。
更新：决定做显而易见的事情，并通过添加四行重复的行来创建pop6()。达到22.8gc，在9.5 s的时间内累加了3840亿个比特。因此，现在还有另外20％的数据在800毫秒处达到320亿比特。
几个未解决的问题：
- 如果数字为负数呢？
- 如果数字为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
一种简单的方法，对于少量的比特应该很好，就像这样(在此示例中为4比特)：
(i＆1)+(i＆2)/ 2 +(i＆4)/ 4 +(i＆8)/ 8
其他人会建议使用少量的位作为简单解决方案吗？
我在1990年左右为RISC机器编写了一个快速的位计数宏。它不使用高级算术(乘法，除法，％)，内存提取(速度太慢)，分支(速度太慢)，但是它确实假定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
因此，如果我采用上面的第一列(A)，将其右移1位，然后从AB中减去，则得到输出(CD)。扩展到3位是相似的。我们可以根据需要使用上面的类似我的8行布尔表进行检查。
- 唐·吉利斯
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);
}
