我有一长串介于 0 和 67600 之间的数字。现在我想使用一个长度为 67600 个元素的数组来存储它们。如果数字在集合中，则元素设置为 1，如果数字不在集合中，则元素设置为 0。 IE。每次我只需要 1 位信息来存储数字的存在。 C/C++ 中是否有任何 hack 可以帮助我实现这一目标？
最佳答案
在 C++ 中，您可以使用 std::vector<bool>如果大小是动态的(它是 std::vector 的特例，请参阅 this )否则有 std::bitset (如果可能，首选 std::bitset。)还有 boost::dynamic_bitset如果您需要在运行时设置/更改大小。你可以找到它的信息here ，很酷!
在 C(和 C++)中，您可以使用按位运算符手动实现这一点。常用操作的一个很好的总结是here .我想提一提的是，在进行位运算时使用无符号整数是个好主意。 <<和 >>移位负整数时未定义。您将需要分配一些整数类型的数组，例如 uint32_t .如果要存储N位，需要 N/32其中uint32_t s。位 i存储在 i % 32 i / 32 的第 ' 位第uint32_t .您可能希望根据您的体系结构和其他约束使用不同大小的整数类型。 注意:更喜欢使用现有的实现(例如，如第一段中描述的 C++，在 Google 中搜索 C 解决方案)而不是滚动自己的实现(除非您特别想要，在这种情况下，我建议了解更多关于在解决这个问题之前从其他地方进行二进制/位操作。)这种事情已经被做死了，并且有“好的”解决方案。
有许多技巧可能只消耗一位:例如位域数组(也适用于 C 语言)，但是否使用更少的空间取决于编译器。见 this link .
请注意，无论您做什么，您几乎肯定永远无法完全使用 N 位来存储 N 位信息 - 您的计算机很可能无法分配少于 8 位的信息:如果如果你想要 7 位，你将不得不浪费 1 位，如果你想要 9 位，你将不得不占用 16 位并浪费其中的 7 位。即使您的计算机(CPU + RAM 等)可以在单个位上“运行”，如果您在具有 malloc 的操作系统中运行。/new由于开销，您的分配器将数据跟踪到如此小的精度是不明智的。最后一个资格非常愚蠢——我想你不会找到一个允许你一次操作少于 8 位的架构:)
关于c++ - C hack 用于存储占用 1 位空间的位？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15483986/