我在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
,我不建议这样做,因为:
*例如,符合标准的函数可以期望&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,但这只会让它更复杂,所以我决定相信自己。
需要了解更多c/c++开发分享C hack用于存储占用1位空间的位?,也可以关注C/ C++技术分享栏目---计算机技术网(www.ctvol.com)!
#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("%dn", 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("%dn", bitsarr_get(&x, i)); bitsarr_delete(x); }
以上就是c/c++开发分享C hack用于存储占用1位空间的位?相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/980512.html