我很感兴趣，想知道在这种情况下计算字节中设置的比特数的最佳方法是什么
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循环中调用此函数应该会产生相当高效的程序。而且它非常通用。
const 默认是 static 的。它们不是吗？ - Rui Monteiro对于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;
}
std::popcount确实是一个很棒的函数。感谢您指出它的存在。然而，当我最初在2015年写下这个答案时，它还没有成为C++标准的一部分。直到C++20才被标准化。 - OmnipotentEntity对于单个字节值，最快的方法是将答案存储在一个256字节数组中，你可以使用该值进行索引。例如：bits_set[] = {0, 1, 1, 2, ...
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 类型，只需简单计算计数值中有多少位，然后在计数循环中使用该值即可。这非常简单。
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;
}
C++20 新增了从头文件 <bit> 引入的 std::popcount
std::popcount(0b1101u) 将返回 3
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
#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;
}
#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;
}();