我有一长串 0 到 67600 之间的数字。现在我想使用一个 67600 个元素长的数组来存储它们。如果某个数字在集合中，则该元素设置为 1；如果该数字不在集合中，则该元素设置为 0。 IE。每次我只需要 1 位信息来存储数字的存在。 C/C++ 中是否有任何 hack 可以帮助我实现这一目标？
在 C++ 中你可以使用std::vector<bool>如果大小是动态的（这是一个特殊情况std::vector, see this http://www.cplusplus.com/reference/vector/vector-bool/）否则有std::bitset（更喜欢std::bitset如果可能的话。）还有boost::dynamic_bitset如果您需要在运行时设置/更改大小。你可以找到相关信息here http://www.boost.org/doc/libs/1_36_0/libs/dynamic_bitset/dynamic_bitset.html，真是太酷了！
在 C（和 C++）中，您可以使用按位运算符手动实现这一点。常见操作的一个很好的总结是here http://en.wikipedia.org/wiki/Bit_manipulation#Bit_manipulation_in_the_C_programming_language。我想提的一件事是，在进行位运算时使用无符号整数是个好主意。<< and >>移位负整数时未定义。您将需要分配某种整数类型的数组，例如uint32_t。如果你想存储N位，这将需要N/32这些uint32_ts. Bit i存储在i % 32的第 1 位i / 32'th uint32_t。您可能希望根据您的体系结构和其他约束使用不同大小的整数类型。Note：更喜欢使用现有的实现（例如，如 C++ 的第一段中所述，在 Google 中搜索 C 解决方案）而不是自行实现（除非您特别想要，在这种情况下，我建议在解决问题之前从其他地方了解更多有关二进制/位操作的信息这个。）这种事已经做死了，也有“好”的解决办法。
有很多技巧可以maybe仅消耗一位：例如位域数组（也适用于 C），但是否使用更少的空间取决于编译器。看这个链接 http://msdn.microsoft.com/en-us/library/yszfawxh%28v=vs.80%29.aspx.
请注意，无论你做什么，你几乎肯定永远无法使用exactlyN 位来存储 N 位信息 - 您的计算机很可能无法分配少于 8 位：如果您想要 7 位，您将不得不浪费 1 位，如果您想要 9 位，您将不得不占用 16 位并浪费其中 7 个。即使您的计算机（CPU + RAM 等）可以在单个位上“运行”，如果您在操作系统中运行malloc/new由于开销，分配器以如此小的精度跟踪数据是不明智的。最后一个资格条件非常愚蠢——我想你不会找到一个允许你一次操作少于 8 位的架构:)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
