计算以字节为单位设置的位数

Question

我感兴趣,这是通过这种方式计算以字节为单位设置的位数的最佳方法

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};
};

也许在运行时知道byte的值是最优的？是否建议在代码中使用它？

Answer 1

对于8位值,只需使用256个元素的查找表.

对于较大尺寸的输入,它稍微不那么简单.Sean Eron Anderson在他的Bit Twiddling Hacks页面上有几个不同的功能,它们都具有不同的性能特征.没有一个全能最快的版本,因为它取决于处理器的性质(管道深度,分支预测器,缓存大小等)和您正在使用的数据.

Answer 2

对于一个字节的数据,考虑速度和内存消耗的最佳方式:

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循环调用此函数应该在大多数系统上产生非常有效的程序.它非常通用.

Answer 3

为什么不使用标准库？这样,最佳方式应该由实现决定,并且可能比您可以实际编写的任何符合标准的代码更好.例如,如果您使用的是x86,则会编译为单个指令,但前提是您的目标是支持它的CPU.

#include <bitset>
#include <iostream>

int main() {
  unsigned char bitfield = 17;
  std::cout << std::bitset<8>(bitfield).count() <<
    std::endl;
}