计算所有设置位的最快方法是什么？

Question

计算所有设置位的最快方法是什么？
我正在计算位的数字是从 1<=n<2^63，只有正值。

目前我使用库中的 bitset，它非常快，但如果有任何更快的选项我想知道。

在最坏的情况下，我有超过 10 亿次迭代，所以我正在寻找加速它的方法。
这是我计算设置位的循环部分：

if (std::bitset<64>(currentNumber).count() == numofOnes)
++counter;

Answer 1

这是平衡查找的演示 table。
这个在节省尺寸方面很重要。
您可以调整概念以查找 tables 的大小，例如64 或 256，大大加快了速度。

#include <iostream>

using namespace std;

int main()
{
   unsigned long long int input=679043ULL; // just a big number, for demo
   
   unsigned char lookup[16]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
   unsigned char result=0;

   while (input>0)
   {
       cout << (unsigned int) result << " " << (input&15) << " " << input << endl;
       result+=lookup[input&15];
       input>>=4;
   }
   cout << (unsigned int)result << endl;
   return 0;
}

输出：

演示输出显示循环累积
“3”中的 2 位，
“8”中的 1 位，
“12”中的 2 位，
“5”中的 2 位，
“10”中的两位；
总共 9.

计算所有设置位的最快方法是什么？

What is the fastest way to count all set bits?

c++

bit-manipulation

bitset