STL bitset::count() 方法的性能如何？

Question

我四处搜寻，找不到 bitset::count() 的性能时间规范。有谁知道它是什么（O(n) 或更好）以及在哪里可以找到它？

编辑通过STL我仅指标准模板库。

Answer 1

我在我的计算机上读取了这个文件（C:\cygwin\lib\gcc\i686-pc-cygwin\3.4.4\include\c++\bitset）。
顺便说一句，请参阅这些

/// Returns the number of bits which are set.
size_t
count() const { return this->_M_do_count(); }      

size_t
_M_do_count() const
{
  size_t __result = 0;
  for (size_t __i = 0; __i < _Nw; __i++)
  __result += __builtin_popcountl(_M_w[__i]);
  return __result;
}

，这是指定 _Nw 的地方：

  template<size_t _Nw>
    struct _Base_bitset

因此在 gcc 实现中它是 O(n) 。我们得出的结论是，规范并不要求它比 O(n) 更好。任何头脑正常的人都不会以比这更糟糕的方式来实施它。然后我们可以放心地假设最坏的情况是 O(n)。可能会更好，但你永远不能指望这一点。

Answer 2

由于 C++ 社区中普遍滥用该术语，我无法确定您在这里所说的“STL”的真正含义。

• C++ 标准 (2003) 没有强制要求std::bitset::count() 的性能（或者，事实上，据我所知，std::bitset 的任何成员）。

• 我也找不到任何建议对 STL 的 bitset::count() 性能进行强制要求的参考资料。

不过，我认为任何理智的实现都会在恒定（或最坏的线性）时间内提供此功能。然而，这只是一种感觉。检查一下你的，看看你实际上会得到什么。

Answer 3

“SGI 的参考实现运行
在线性时间内相对于
需要存储的字节数
位。它通过创建一个
256 个整数的静态数组。这
存储在数组中第 i 个索引处的值
是值中设置的位数
我。”

http://www.cplusplus.com/forum/general/12486/

Answer 4

我不确定您是否会找到相应的规范，因为 STL 通常不需要一定程度的性能。我已经看到暗示它“快”，在集合的大小中每个比特大约 1 个周期。您当然可以阅读特定实现的代码以了解所期望的内容。

Answer 5

我们遵循的算法是对所有设置为 1 的位进行计数。
现在，如果我们想对数字 n 的位集进行计数，我们将遍历 log(n)+1 位数字。

例如：对于数字 13，我们得到 1101 作为位集。

13 的自然对数 = 2.564（大约） 3

位数 = 3+1 = 4

对于任何数字 n（十进制），我们循环 log(n)+1 次。

另一种方法如下：

int count_set_bits_fast(int n) {
int count = 0;
while (n > 0) {
    n=(n&(n-1));
    count++
}

return count;
}

如果分析功能线 n=(n&(n-1));你会发现它本质上减少了从右到左的位数。

因此，顺序将是总设置位数。

例如： 13 = 1101

1101&1100 = 1100

1100&1011 = 1000

1000&0111 = 0

O(设置位数), O(Log(n)+1) 最坏情况