c++ - 使用位集存储位图有什么好处？

Question

我目前正在评估是应该使用单个大位集还是多个 64 位无符号长整型 (uint_64) 来存储大量位图信息。在这种情况下，位图表示几 GB 内存页面的当前状态(脏/不脏)，并且有数千个条目。

我正在执行的工作要求我能够查询和更新脏页，包括在两个脏页位图之间执行 OR 运算。

明确地说，我将执行以下操作:

• 从文件中导入位图，并与现有位图进行按位或操作
• 计算汉明权重(统计设置为1的位数，代表脏页的个数)
• 重置/清除一点，将其标记为已更新/干净
• 检查钻头的当前状态，判断它是否干净

看起来很容易对 C++ 位集执行位运算，并且很容易计算汉明权重。但是，我认为这里没有魔法——CPU 只能对寄存器中存储的尽可能多的字节执行按位运算——因此位集使用的例程可能与我自己实现的例程相同。汉明权重可能也是如此。

此外，将位图数据从文件导入到位集看起来很难看——我需要多次执行位移位，如图所示here .我想考虑到我将使用的位集的大小，这会对性能产生负面影响。当然，我想我可以改用许多小的位集，但这可能没有任何优势(除了易于实现之外)。

我们一如既往地采纳任何建议。谢谢!

Answer 1

听起来您有一个非常具体的一次性应用程序。就我个人而言，我从未使用过位集，但据我所知，它的优势在于可以像 bool 数组一样访问，并且能够像 vector 一样动态增长。

据我所知，您实际上并不需要其中任何一个。如果是这种情况，并且如果填充位集是一出戏剧，我会倾向于自己做，因为分配一大堆整数并对它们进行位运算确实非常简单。

鉴于有非常具体的要求，您可能会从自己的优化中受益。能够访问原始位数据对此至关重要(例如，使用预先计算的汉明权重表来处理单个字节，如果您有空闲内存，甚至可以使用两个字节)。

我一般不提倡重新发明轮子……但如果您有特殊的优化要求，最好针对这些要求定制您的解决方案。在这种情况下，您要实现的功能非常简单。