我很感兴趣，这是通过这种方式计算以字节为单位的位数的最佳方法
template< unsigned char byte > class BITS_SET
{
public:
enum {
B0 = (byte & 0x01) ? 1:0,
B1 = (byte & 0x02) ? 1:0,
B2 = (byte & 0x04) ? 1:0,
B3 = (byte & 0x08) ? 1:0,
B4 = (byte & 0x10) ? 1:0,
B5 = (byte & 0x20) ? 1:0,
B6 = (byte & 0x40) ? 1:0,
B7 = (byte & 0x80) ? 1:0
};
public:
enum{RESULT = B0+B1+B2+B3+B4+B5+B6+B7};
};
当字节的值在运行时已知时，也许它是最佳的？是否建议在代码中使用它？
对于一个字节的数据，考虑速度和内存消耗的最佳方式：
uint8_t count_ones (uint8_t byte)
{
static const uint8_t NIBBLE_LOOKUP [16] =
{
0, 1, 1, 2, 1, 2, 2, 3,
1, 2, 2, 3, 2, 3, 3, 4
};
return NIBBLE_LOOKUP[byte & 0x0F] + NIBBLE_LOOKUP[byte >> 4];
}
在大多数系统上，从 for 循环调用这个函数应该会产生一个相当高效的程序。它非常通用。
对于 8 位值，只需使用 256 个元素的查找表。
对于更大尺寸的输入，它稍微不那么琐碎。Sean Eron Anderson 在他的Bit Twiddling Hacks 页面上为此提供了几种不同的功能，它们都具有不同的性能特征。没有一个最快的版本，因为它取决于您的处理器的性质（管道深度、分支预测器、缓存大小等）和您正在使用的数据。
为什么不直接使用标准库？这样，最佳方式应由实现确定，并且可能比您实际编写的任何符合标准的代码更好。例如，如果您在 x86 上，这将编译为一条指令，但前提是您的目标是支持它的 CPU。
#include <bitset>
#include <iostream>
int main() {
unsigned char bitfield = 17;
std::cout << std::bitset<8>(bitfield).count() <<
std::endl;
}
对于单个字节值，最快的方法是将答案存储在一个 256 字节数组中，并用该值作为索引。例如，bits_set[] = {0, 1, 1, 2, ...
“进行位计数的最快方法”的通常答案是“在数组中查找字节”。这种方法适用于字节，但您需要为它支付实际的内存访问费用。如果您只偶尔执行一次，它可能是最快的，但如果您只偶尔执行一次，则不需要最快。
如果你经常这样做，你最好将字节分批成字或双字，并对它们进行快速的位计数操作。这些往往是纯算术，因为您实际上无法在数组中查找 32 位值以获取其位数。相反，您可以通过巧妙的方式移动和屏蔽来组合值。
一个很好的聪明技巧来源是Bit Hacks。
这是那里发布的用于计算 C 中 32 位字中的位的方案：
unsigned int v; // count bits set in this (32-bit value)
unsigned int c; // store the total here
v = v - ((v >> 1) & 0x55555555); // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
为什么不进行左移并屏蔽其余部分？
int countBits(unsigned char byte){
int count = 0;
for(int i = 0; i < 8; i++)
count += (byte >> i) & 0x01; // Shift bit[i] to the first position, and mask off the remaining bits.
return count;
}
通过简单地计算正在计数的值中有多少位，然后在计数器循环中使用该值，这可以很容易地适应处理任何大小的整数。这一切都是微不足道的。
int countBits(unsigned long long int a){
int count = 0;
for(int i = 0; i < sizeof(a)*8; i++)
count += (a >> i) & 0x01;
return count;
}
#include <iostream>
#include <climits> // for CHAR_BIT (most likely to be 8)
#include <cstring> // for memset
#include <new>
static const int DUMMY = -1;
// first approch : activate the O(8) function in first get try... after that its O(1);
class bitsInByteflyLUT
{
typedef unsigned char byte;
public:
bitsInByteflyLUT(); //CTOR - throws std::bad_alloc
~bitsInByteflyLUT(); //DTOR
int Get_bitsInByte(byte _byte);
private:
// CLASS DATA
int* flyLUT;
// PRIVATE FUNCTIONS
int bitsInByte(byte _byte);
// O(8) for finding how many bits are ON in a byte.
// answer can be between 0 to CHAR_BIT.
bitsInByteflyLUT(const bitsInByteflyLUT & _class); // COPY CTOR - forbidden
const bitsInByteflyLUT & operator= (const bitsInByteflyLUT& _class);
// ASSIGN OPERATOR - forbidden
};
bitsInByteflyLUT::bitsInByteflyLUT()
{
size_t nIndexes = 1 << CHAR_BIT;
try
{
flyLUT = new int[nIndexes];
}
catch (std::bad_alloc& ba)
{
throw;
}
memset(flyLUT, DUMMY, sizeof(int)*nIndexes);
}
bitsInByteflyLUT::~bitsInByteflyLUT()
{
delete[] flyLUT;
}
int bitsInByteflyLUT::Get_bitsInByte(byte _byte)
{
if (flyLUT[_byte] == DUMMY) // if its first time we try to get answer for this char.
{
flyLUT[_byte] = bitsInByte(_byte); // O(8)
}
return flyLUT[_byte]; // O(1)
}
int bitsInByteflyLUT::bitsInByte(byte _byte)
{
byte nBits = CHAR_BIT;
byte counter = 0;
byte mask = 1;
while(nBits--)
{
if(mask & _byte)
{
++counter;
}
mask <<= 1;
}
return counter;
}
int main ()
{
using std::cout;
using std::endl;
bitsInByteflyLUT flut;
for (unsigned int i = 0; i < (1 << CHAR_BIT); i += 1)
{
cout << i << " " << flut.Get_bitsInByte(i) << endl;
}
return 0;
}
使用 C++17，您可以使用 constexpr lambda 预先计算查找表。比现成的复制粘贴表更容易推理它的正确性。
#include <array>
#include <cstdint>
static constexpr auto bitsPerByteTable = [] {
std::array<uint8_t, 256> table{};
for (decltype(table)::size_type i = 0; i < table.size(); i++) {
table.at(i) = table.at(i / 2) + (i & 1);
}
return table;
}();
std::popcount从头文件介绍的C++20<bit>
std::popcount(0b1101u)将返回 3
有关更多详细信息，请参阅https://en.cppreference.com/w/cpp/numeric/popcount。
int count(int a){ return a == 0 ? 0 : 1 + count(a&(a-1)); }
在 gcc 中，您可以使用 __builtin_popcount(unsigned) 函数。
它应该有效地使用目标硬件平台的最佳解决方案。
使用 -march=core-avx2 （与我的 cpu 兼容的最高级别），使用 popcntl x86_64 汇编指令，在硬件中执行此操作。
使用默认的 x86_64 指令集，调用了一个 popcntl 函数，该函数实现了最优的 C（聪明的 hacks）算法。
还有 __builtin_popcountl 和 __builtin_popcountll 用于 unsigned long 和 unsigned long long。
#include <ctime>
#include <iostream>
using namespace std;
int count1s(unsigned char byte) {
if (byte == 0) {
return 0;
}
if (byte & 0x01) {
return 1 + count1s(byte >> 1);
}
return count1s(byte >> 1);
}
int count1s2(unsigned char byte) {
static const int ones[256] = {
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};
return ones[(int)byte];
}
int main() {
time_t start = clock();
int c = count1s(205);
time_t end = clock();
cout << "count1: " << c << " time: " << double(end - start) << endl;
start = clock();
c = count1s2(205);
end = clock();
cout << "count2: " << c << " time: " << double(end - start) << endl;
return 0;
}