13

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

由 STL编辑我只指标准模板库。

4

5 回答 5

11

我在我的电脑上阅读了这个文件（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)。可能更好，但你永远不能指望它。

于 2011-01-14T17:14:13.303 回答
1

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

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

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

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

于 2011-01-14T17:16:40.273 回答
0

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

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

于 2011-01-14T17:08:20.473 回答
0

我不确定您是否会为此找到规范，因为 STL 通常不需要一定的性能水平。我已经看到它“快速”的提示，在集合的大小中每比特大约 1 个周期。您当然可以阅读您的特定实现的代码以了解预期结果。

于 2011-01-14T17:09:43.227 回答
0

我们遵循的算法是计算所有设置为 1 的位。现在，如果我们想通过该位集来计算数字 n，我们将通过 log(n)+1 位。

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

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）最坏情况

于 2021-08-06T03:02:41.733 回答