C hack用于存储占用1位空间的位？
我在0到67600之间有一长串数字。现在我想使用长度为67600个元素的数组存储它们。 如果数字在集合中，则元素设置为1;如果数字不在集合中，则设置为0。 即。 每次我只需要1位信息来存储一个数字。 C / C ++中是否存在帮助我实现这一目标的黑客攻击？
在C ++中你可以使用std::vector如果大小是动态的（这是std::vector的一个特例，请看这个 ），否则就有std::bitset （如果可能的话，更喜欢std::bitset 。）有如果需要在运行时设置/更改大小，还可以使用boost::dynamic_bitset 。 你可以在这里找到相关信息，非常酷！
在C（和C ++）中，您可以使用按位运算符手动实现此操作。 这里是常见操作的一个很好的总结。 我想提到的一件事是在进行位操作时使用无符号整数是一个好主意。 当移位负整数时， <<和>>是未定义的。 您将需要分配某些整数类型的数组，如uint32_t 。 如果要存储N位，则需要这些uint32_t的N/32 。 比特i存储在第i / 32号uint32_t的第i % 32位。 您可能希望使用不同大小的整数类型，具体取决于您的体系结构和其他约束。 注意 ：更喜欢使用现有的实现（例如，在C ++的第一段中描述，搜索Google的C解决方案）而不是自己编写（除非您特别想要，在这种情况下，我建议在以前从其他地方学习更多关于二进制/位操作的知识）解决这个问题。）这种事情已经完成了死亡并且有“好”的解决方案。
有许多技巧可能只消耗一位：例如位域数组（也适用于C），但是否使用的空间是否由编译器决定。 看到这个链接 。
请注意，无论你做什么，你几乎肯定永远不能使用正好 N位来存储N位信息 - 你的计算机很可能不能分配少于8位：如果你想要7位，你将不得不浪费1位，如果你想要9，你将需要16位并浪费其中的7位。 即使你的计算机（CPU + RAM等）可以在单个位上“操作”，如果你在带有malloc / new的操作系统中运行，你的分配器也不会因为开销而将数据跟踪到如此小的精度。 最后一个资格非常愚蠢 - 你不会发现一个正在使用的架构允许你在我想象的时间内以低于8位的速度运行:)
你应该使用std::bitset 。
std::bitset函数类似于bool数组（实际上类似于std::array ，因为它按值复制），但每个元素只使用1位存储空间。
另一个选项是vector ，我不建议这样做，因为：
- 它使用较慢的指针间接和堆内存来启用resize，这是您不需要的。
- 这种类型经常受到标准纯粹主义者的诽谤，因为它声称是标准容器，但不遵守标准容器*的定义。
*例如，符合标准的函数可以期望&container.front()生成指向任何容器类型的第一个元素的指针，该指针因std::vector而失败。 也许是你用例的挑剔，但仍然值得了解。
实际上有！ std::vector有一个专门化： http ： //en.cppreference.com/w/cpp/container/vector_bool
查看文档，它尽可能高效地存储它。
编辑：正如其他人所说， std::bitset也可用： http ： //en.cppreference.com/w/cpp/utility/bitset
如果要在C中写入，请使用长度为67601位的char数组（67601/8 = 8451），然后为每个值打开/关闭相应的位。
其他人给出了正确的想法。 这是我自己实现的bitsarr或’数组’位。 unsigned char是一个字节，因此它本质上是一个无符号字符数组，用于将信息存储在各个位中。 我添加了除了一位值之外还存储两个或四个位值的选项，因为它们都除以8（一个字节的大小），如果你想存储大量范围为0的整数，这将是有用的。 -3或0-15。
设置和获取时，数学在函数中完成，因此你可以给它一个索引，好像它是一个普通的数组 – 它知道在哪里看。
此外，用户有责任不传递值来设置太大，否则会搞砸其他值。 它可以被修改，以便溢出循环回到0，但这只会让它更复杂，所以我决定相信自己。
#include #include #define BYTE 8 typedef enum {ONE=1, TWO=2, FOUR=4} numbits; typedef struct bitsarr{ unsigned char* buckets; numbits n; } bitsarr; bitsarr new_bitsarr(int size, numbits n) { int b = sizeof(unsigned char)*BYTE; int numbuckets = (size*n + b - 1)/b; bitsarr ret; ret.buckets = malloc(sizeof(ret.buckets)*numbuckets); ret.n = n; return ret; } void bitsarr_delete(bitsarr xp) { free(xp.buckets); } void bitsarr_set(bitsarr *xp, int index, int value) { int buckdex, innerdex; buckdex = index/(BYTE/xp->n); innerdex = index%(BYTE/xp->n); xp->buckets[buckdex] = (value << innerdex*xp->n) | ((~(((1 << xp->n) - 1) << innerdex*xp->n)) & xp->buckets[buckdex]); //longer version /*unsigned int width, width_in_place, zeros, old, newbits, new; width = (1 << xp->n) - 1; width_in_place = width << innerdex*xp->n; zeros = ~width_in_place; old = xp->buckets[buckdex]; old = old & zeros; newbits = value << innerdex*xp->n; new = newbits | old; xp->buckets[buckdex] = new; */ } int bitsarr_get(bitsarr *xp, int index) { int buckdex, innerdex; buckdex = index/(BYTE/xp->n); innerdex = index%(BYTE/xp->n); return ((((1 << xp->n) - 1) << innerdex*xp->n) & (xp->buckets[buckdex])) >> innerdex*xp->n; //longer version /*unsigned int width = (1 << xp->n) - 1; unsigned int width_in_place = width << innerdex*xp->n; unsigned int val = xp->buckets[buckdex]; unsigned int retshifted = width_in_place & val; unsigned int ret = retshifted >> innerdex*xp->n; return ret; */ } int main() { bitsarr x = new_bitsarr(100, FOUR); for(int i = 0; i<16; i++) bitsarr_set(&x, i, i); for(int i = 0; i<16; i++) printf("%d\n", bitsarr_get(&x, i)); for(int i = 0; i<16; i++) bitsarr_set(&x, i, 15-i); for(int i = 0; i<16; i++) printf("%d\n", bitsarr_get(&x, i)); bitsarr_delete(x); }