代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
这就是所谓的“汉明权重”,“popcount”或“横向相加”。
一些cpu有单独的内置指令来做这件事,而另一些cpu有并行指令来处理位向量。像x86的popcnt(在支持它的cpu上)这样的指令几乎肯定对单个整数来说是最快的。其他一些架构可能有一个缓慢的指令,实现了一个微编码循环,每个周期测试一个比特(需要引用-硬件popcount通常是快速的,如果它存在的话。)
“最佳”算法实际上取决于你所使用的CPU以及你的使用模式。
Your compiler may know how to do something that's good for the specific CPU you're compiling for, e.g. C++20 std::popcount(), or C++ std::bitset<32>::count(), as a portable way to access builtin / intrinsic functions (see another answer on this question). But your compiler's choice of fallback for target CPUs that don't have hardware popcnt might not be optimal for your use-case. Or your language (e.g. C) might not expose any portable function that could use a CPU-specific popcount when there is one.
不需要(或受益于)任何硬件支持的可移植算法
如果您的CPU有一个很大的缓存,并且您在一个紧密的循环中执行大量这些操作,那么预先填充的表查找方法可以非常快。然而,它可能会因为“缓存丢失”的代价而受到影响,在这种情况下,CPU必须从主存中获取一些表。(分别查找每个字节以保持表小。)如果你想要popcount的连续范围的数字,只有低字节改变的组256个数字,这是非常好的。
如果你知道你的字节大部分是0或1,那么就有针对这些情况的有效算法,例如在循环中使用bithack清除最低的集合,直到它变成0。
我相信一个非常好的通用算法是以下,称为“并行”或“可变精度SWAR算法”。我已经在一个类似C的伪语言中表达了这一点,你可能需要调整它以适用于特定的语言(例如使用uint32_t for c++和>>> in Java):
GCC10和clang 10.0可以识别这种模式/习惯用法,并在可用时将其编译为硬件popcnt或等效指令,为您提供两全其美的服务。(https://godbolt.org/z/qGdh1dvKK)
int numberOfSetBits(uint32_t i)
{
// Java: use int, and use >>> instead of >>. Or use Integer.bitCount()
// C or C++: use uint32_t
i = i - ((i >> 1) & 0x55555555); // add pairs of bits
i = (i & 0x33333333) + ((i >> 2) & 0x33333333); // quads
i = (i + (i >> 4)) & 0x0F0F0F0F; // groups of 8
return (i * 0x01010101) >> 24; // horizontal sum of bytes
}
对于JavaScript:强制为整数|0的性能:更改第一行为i = (i|0) - ((i >> 1) & 0x55555555);
这是所有讨论过的算法中最糟糕的行为,因此可以有效地处理您抛出的任何使用模式或值。(它的性能不依赖于普通cpu的数据,在普通cpu中,包括乘法在内的所有整数操作都是常量时间。“简单”输入不会让它变得更快,但它仍然相当不错。)
引用:
https://graphics.stanford.edu/~seander/bithacks.html https://catonmat.net/low-level-bit-hacks用于bithack基础知识,例如如何减去1翻转连续的零。 https://en.wikipedia.org/wiki/Hamming_weight http://gurmeet.net/puzzles/fast-bit-counting-routines/ http://aggregate.ee.engr.uky.edu/MAGIC/人口% 20计数% 20(% 20计数)
这个SWAR bithack如何工作:
i = i - ((i >> 1) & 0x55555555);
第一步是屏蔽的优化版本,以隔离奇数/偶数位,移动以对齐它们,并添加。这有效地在2位累加器(SWAR = SIMD Within A Register)中进行16个独立的加法。比如(i & 0x55555555) + ((i>>1) & 0x55555555)。
下一步是取这16个2位累加器中的奇/偶8个,然后再次相加,得到8个4位累加器。我…这次不可能进行优化,所以它只是在移动之前/之后进行遮罩。使用相同的0x33…两次都是常量,而不是0xccc…在为需要单独在寄存器中构造32位常量的isa编译时,在移位之前进行转换是一件好事。
(i + (i >> 4)) & 0x0F0F0F0F的最后一个移位和添加步骤将扩大为4个8位累加器。它在加后而不是加前进行掩码,因为如果设置了所有对应的4位输入位,则任何4位累加器中的最大值为4。4+4 = 8仍然适合4位,所以在I + (I >> 4)中,啃食元素之间的进位是不可能的。
到目前为止,这只是使用SWAR技术和一些聪明的优化的相当普通的SIMD。继续相同的模式2步可以扩大到2x 16位,然后1x 32位计数。但在硬件快速相乘的机器上,有一种更有效的方法:
一旦我们有足够少的“元素”,一个神奇常数的乘法可以把所有的元素加起来变成最上面的元素。在本例中是字节元素。乘法是通过左移和加法完成的,因此x * 0x01010101的乘法得到x + (x<<8) + (x<<16) + (x<<24)。我们的8位元素足够宽(并且包含足够小的计数),因此不会产生进位到前8位。
它的64位版本可以使用0x0101010101010101乘数在64位整数中处理8x 8位元素,并使用>>56提取高字节。所以它不需要任何额外的步骤,只是更大的常数。这是当硬件popcnt指令未启用时,GCC在x86系统上对__builtin_popcountll使用的方法。如果您可以为此使用内置或内在函数,那么这样做可以让编译器有机会进行特定于目标的优化。
对于更宽的向量具有完整的SIMD(例如计算整个数组)
这种逐位swar算法可以在多个向量元素中同时进行并行运算,而不是在单个整数寄存器中进行并行运算,从而在具有SIMD但没有可用popcount指令的cpu上实现加速。(例如x86-64代码必须在任何CPU上运行,而不仅仅是Nehalem或更高版本。)
然而,对popcount使用矢量指令的最佳方法通常是使用变量-shuffle并行地对每个字节每次4位进行表查找。(4位索引保存在向量寄存器中的16项表)。
在Intel cpu上,硬件64位popcnt指令的性能比SSSE3 PSHUFB位并行实现的性能好2倍,但前提是编译器的性能恰到好处。否则,上交所可能会大幅领先。较新的编译器版本意识到popcnt对Intel的错误依赖问题。
https://github.com/WojciechMula/sse-popcount state-of-the-art x86 SIMD popcount for SSSE3, AVX2, AVX512BW, AVX512VBMI, or AVX512 VPOPCNT. Using Harley-Seal across vectors to defer popcount within an element. (Also ARM NEON) Counting 1 bits (population count) on large data using AVX-512 or AVX-2 related: https://github.com/mklarqvist/positional-popcount - separate counts for each bit-position of multiple 8, 16, 32, or 64-bit integers. (Again, x86 SIMD including AVX-512 which is really good at this, with vpternlogd making Harley-Seal very good.)
其他回答
大约在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行布尔表来检查它。
不吉利
为什么不迭代地除以2呢?
count = 0 while n > 0 if (n % 2) == 1 count += 1 n /= 2
我同意这不是最快的,但是“最好”这个词有点含糊不清。我认为“最好”应该有一个清晰的元素
有些语言以一种可以使用有效硬件支持(如果可用的话)的方式可移植地公开操作,而有些语言则希望使用一些不错的库。
例如(从语言表中):
c++有std::bitset<>::count()或c++ 20 std::popcount(T x) Java有Java .lang. integer . bitcount()(也用于Long或BigInteger) c#有system . numbers . bitoperations . popcount () Python有int.bit_count()(从3.10开始)
不过,并不是所有的编译器/库都能在HW支持可用时使用它。(值得注意的是MSVC,即使有选项使std::popcount内联为x86 popcnt,它的std::bitset::count仍然总是使用查找表。这有望在未来的版本中改变。)
当可移植语言没有这种基本的位操作时,还要考虑编译器的内置函数。以GNU C为例:
int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);
In the worst case (no single-instruction HW support) the compiler will generate a call to a function (which in current GCC uses a shift/and bit-hack like this answer, at least for x86). In the best case the compiler will emit a cpu instruction to do the job. (Just like a * or / operator - GCC will use a hardware multiply or divide instruction if available, otherwise will call a libgcc helper function.) Or even better, if the operand is a compile-time constant after inlining, it can do constant-propagation to get a compile-time-constant popcount result.
GCC内置甚至可以跨多个平台工作。Popcount几乎已经成为x86架构的主流,所以现在开始使用内置是有意义的,这样你就可以重新编译,让它内联硬件指令时,你编译-mpopcnt或包括(例如https://godbolt.org/z/Ma5e5a)。其他架构已经有popcount很多年了,但在x86领域,仍然有一些古老的Core 2和类似的老式AMD cpu在使用。
在x86上,你可以告诉编译器它可以通过-mpopcnt(也可以通过-msse4.2暗示)假设支持popcnt指令。参见GCC x86选项。-march=nehalem -mtune=skylake(或-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可能会更好。
For target architectures where hardware popcount is an optional extension (like x86), not all compilers have a std::bitset that takes advantage of it when available. For example, MSVC has no way to enable popcnt support at compile time, and it's std::bitset<>::count always uses a table lookup, even with /Ox /arch:AVX (which implies SSE4.2, which in turn implies the popcnt feature.) (Update: see below; that does get MSVC's C++20 std::popcount to use x86 popcnt, but still not its bitset<>::count. MSVC could fix that by updating their standard library headers to use std::popcount when available.)
但是,至少您得到了可以在任何地方工作的可移植的东西,并且使用带有正确目标选项的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 # unnecessary 64-bit operand size
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发出(对于int arg版本):
rldicl 3,3,0,32 # zero-extend from 32 to 64-bit
popcntd 3,3 # popcount
blr
这个源代码不是x86特定的,也不是gnu特定的,只是在gcc/clang/icc下编译得很好,至少在针对x86(包括x86-64)时是这样。
还要注意,对于没有单指令popcount的体系结构,gcc的回退是逐字节表查找。例如,这对ARM来说就不是什么好事。
c++ 20有std::popcount(T)
不幸的是,当前libstdc++头文件用特殊情况定义了它,if(x==0) return 0;在开始时,clang在编译x86时不会优化:
#include <bit>
int bar(unsigned x) {
return std::popcount(x);
}
clang 11.0.1 -O3 -std=gnu++20 -march=nehalem (https://godbolt.org/z/arMe5a)
# clang 11
bar(unsigned int): # @bar(unsigned int)
popcnt eax, edi
cmove eax, edi # redundant: if popcnt result is 0, return the original 0 instead of the popcnt-generated 0...
ret
但是GCC编译得很好:
# gcc 10
xor eax, eax # break false dependency on Intel SnB-family before Ice Lake.
popcnt eax, edi
ret
即使是MSVC也能很好地使用它,只要你使用-arch:AVX或更高版本(并使用-std:c++latest启用c++ 20)。https://godbolt.org/z/7K4Gef
int bar(unsigned int) PROC ; bar, COMDAT
popcnt eax, ecx
ret 0
int bar(unsigned int) ENDP ; bar
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);
}
摘自《黑客的喜悦》第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条指令(依赖于arch),没有分支。黑客的喜悦是令人愉快的!强烈推荐。