代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
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.0带有g++-9 -std=c++2a仍然不支持它。
提案说:
标题:< > 命名空间STD { // 25.5.6,计数 模板类T > < conexpr int popcount(T x) noexcept;
and:
模板类T > < conexpr int popcount(T x) noexcept; 约束:T是无符号整数类型(3.9.1 [basic.fundamental])。 返回:x值中的1位数。
std::rotl和std::rotr也被添加来执行循环位旋转:c++中循环移位(旋转)操作的最佳实践
其他回答
public class BinaryCounter {
private int N;
public BinaryCounter(int N) {
this.N = N;
}
public static void main(String[] args) {
BinaryCounter counter=new BinaryCounter(7);
System.out.println("Number of ones is "+ counter.count());
}
public int count(){
if(N<=0) return 0;
int counter=0;
int K = 0;
do{
K = biggestPowerOfTwoSmallerThan(N);
N = N-K;
counter++;
}while (N != 0);
return counter;
}
private int biggestPowerOfTwoSmallerThan(int N) {
if(N==1) return 1;
for(int i=0;i<N;i++){
if(Math.pow(2, i) > N){
int power = i-1;
return (int) Math.pow(2, power);
}
}
return 0;
}
}
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;
}
我来解释一下这个算法。
该算法基于分治算法。假设有一个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)
+-------------------------------+
有些语言以一种可以使用有效硬件支持(如果可用的话)的方式可移植地公开操作,而有些语言则希望使用一些不错的库。
例如(从语言表中):
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
我认为最快的方法——不使用查找表和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 ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
它之所以有效,是因为你可以通过将设置位分为两半来计算总设置位的数量,计算两半设置位的数量,然后将它们相加。也被称为分而治之范式。让我们来详细谈谈。
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),则产生0b01,否则产生0b00。
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
这句话应该很容易理解。在第一个操作之后,我们每两个比特中就有一个set位的计数,现在我们每4个比特中就有一个set位的计数。
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位设置。现在我们把这些小块加在一起。
v = 0b01000010
(v >> 4) = 0b00000100
v + (v >> 4) = 0b01000010 + 0b00000100
它为我们提供了一个字节中set位的计数,在第二个nibble 0b01000110中,因此我们掩码了该数字中所有字节的前四个字节(丢弃它们)。
0b01000110 & 0x0F = 0b00000110
现在每个字节都有一个集合位的计数。我们需要把它们全部加起来。诀窍是将结果乘以0b10101010,它有一个有趣的属性。如果我们的数字有四个字节,A B C D,它将产生一个新的数字,包含这些字节A+B+C+D B+C+D C+D。一个4字节的数字最多可以设置32位,可以表示为0b00100000。
我们现在需要的是第一个字节,它是所有字节中所有set位的和,我们通过>> 24得到它。该算法是为32位字设计的,但可以很容易地修改为64位字。
这也可以正常工作:
int ans = 0;
while(num) {
ans += (num & 1);
num = num >> 1;
}
return ans;