C / C ++位数组或位向量
我正在学习C / C ++编程并遇到过“位数组”或“位向量”的用法。 我无法理解他们的目的？ 这是我的疑惑 –
- 它们是否用作布尔标志？
- 可以使用
int数组吗？ （当然更多的记忆，但..） - 这个Bit-Masking的概念是什么？
- 如果位掩码是简单的位操作以获得适当的标志，那么如何为它们编程？ 是不是很难在头脑中做这个操作，看看标志会是什么，与十进制数相对应？
我正在寻找应用程序，以便我能更好地理解。 对于Eg –
问：您将获得一个包含范围内的整数（1到1百万）的文件。 有一些重复，因此缺少一些数字。 找到找到丢失数字的最快方法？
对于上面的问题，我已经阅读了解决方案，告诉我使用位数组。 如何将每个整数存储一下？
我认为你已经把数组和数字混淆了，特别是操纵二进制数字意味着什么。
我将以身作则。 假设您有许多错误消息，并且希望以函数的返回值返回它们。 现在，您可以标记您的错误1,2,3,4 …这对您的想法有意义，但是如果只给出一个数字，您如何计算出发生了哪些错误？
现在，尝试标记错误1,2,4,8,16 ……基本上增加2的幂。 为什么这样做？ 好吧，当你工作基地2时，你正在操纵一个像00000000这样的数字，其中每个数字对应于2的幂乘以它从右边的位置。 因此，假设出现错误1,4和8。 那么，那可以表示为00001101 。 相反，第一个数字= 1 * 2 ^ 0，第三个数字1 * 2 ^ 2和第四个数字1 * 2 ^ 3。 将它们全部添加为13。
现在，我们可以通过应用位掩码来测试是否发生了这样的错误。 例如，如果您想在错误8发生时计算出来，请使用8 = 00001000的位表示。 现在，为了提取是否发生了错误，请使用二进制文件，如下所示：
00001101 & 00001000 = 00001000
我确定你知道如何工作或者可以从上面推断 – 工作数字，如果任何两位数都是1，结果是1，否则它是0。
现在，在C：
int func(...) { int retval = 0; if ( sometestthatmeans an error ) { retval += 1; } if ( sometestthatmeans an error ) { retval += 2; } return retval } int anotherfunc(...) { uint8_t x = func(...) /* binary and with 8 and shift 3 plaes to the right * so that the resultant expression is either 1 or 0 */ if ( ( ( x & 0x08 ) >> 3 ) == 1 ) { /* that error occurred */ } }
现在，实用性。 当内存稀疏且协议没有冗长的冗长xml等时，通常将字段划分为如此多的位宽。 在该字段中，您将各种位（标志，2的幂）分配给某个含义，并应用二进制操作来推断它们是否已设置，然后对这些操作进行操作。
我还应该补充说，二进制操作与计算机的底层电子设备关系密切。 想象一下，如果位字段对应于各种电路的输出（携带电流与否）。 通过使用所述电路的足够组合，您可以制作一台计算机。
关于bits数组的用法：
如果你知道“只有”100万个数字 – 你使用一个100万位的数组。 在开始时，所有位都将为零，并且每次读取数字时 – 使用此数字作为索引并将此索引中的位更改为1（如果它已经不是一个）。
读完所有数字后 – 缺少的数字是数组中零的索引。
例如，如果我们只有0到4之间的数字，则数组在开头看起来像这样：0 0 0 0 0.如果我们读取数字：3,2,2数组看起来像这样：读3 – > 0 0 0 1 0.读取3（再次） – > 0 0 0 1 0.读取2 – > 0 0 1 1 0.检查零的索引：0,1,4 – 这些是缺失的数字
BTW，当然你可以使用整数而不是位，但它可能需要（取决于系统）32次内存
斯万
位数组或位向量可以作为布尔值数组 。 通常，布尔变量至少需要一个字节存储，但在位数组/向量中只需要一位。 如果您有大量此类数据，这样可以节省大量内存。
另一种用法是，如果您的数字不完全适合大小为8,16,32或64位的标准变量 。 你可以通过这种方式存储一个16位的位向量，一个由4位组成的数字，一个是2位，一个是10位。 通常，您必须使用大小为8,8和16位的3个变量，因此您只有50％的存储空间被浪费。
但是所有这些用途在业务应用中很少使用，经常在通过pinvoke / interop函数连接驱动程序并进行低级编程时使用 。
比特矢量的比特arrays用作从位置到某个比特值的映射。 是的，它与Bool数组基本相同，但典型的Bool实现长度为1到4个字节，并且占用太多空间。
我们可以通过使用单词数组和二进制掩码操作以及转换来存储和检索它们来更有效地存储相同数量的数据（使用的内存更少，内存访问更少，缓存未命中更少，内存页交换更少）。 访问各个位的代码仍然非常简单。
还有一些用C语言内置的位字段支持（你写的东西比如int i:1;说“只消耗一位”），但它不适用于数组，你对整体结果的控制较少（详情见实现取决于编译器和对齐问题）。
以下是回答“搜索缺失数字”问题的可能方法。 我将int大小固定为32位以保持简单，但可以使用sizeof（int）编写它以使其可移植。 并且（取决于编译器和目标处理器）代码只能使用>> 5而不是/ 32和& 31而不是% 32来更快，但这只是为了给出这个想法。
#include #include #include int main(){ /* put all numbers from 1 to 1000000 in a file, except 765 and 777777 */ { printf("writing test file\n"); int x = 0; FILE * f = fopen("testfile.txt", "w"); for (x=0; x < 1000000; ++x){ if (x == 765 || x == 777760 || x == 777791){ continue; } fprintf(f, "%d\n", x); } fprintf(f, "%d\n", 57768); /* this one is a duplicate */ fclose(f); } uint32_t bitarray[1000000 / 32]; /* read file containing integers in the range [1,1000000] */ /* any non number is considered as separator */ /* the goal is to find missing numbers */ printf("Reading test file\n"); { unsigned int x = 0; FILE * f = fopen("testfile.txt", "r"); while (1 == fscanf(f, " %u",&x)){ bitarray[x / 32] |= 1 << (x % 32); } fclose(f); } /* find missing number in bitarray */ { int x = 0; for (x=0; x < (1000000 / 32) ; ++x){ int n = bitarray[x]; if (n != (uint32_t)-1){ printf("Missing number(s) between %d and %d [%x]\n", x * 32, (x+1) * 32, bitarray[x]); int b; for (b = 0 ; b < 32 ; ++b){ if (0 == (n & (1 << b))){ printf("missing number is %d\n", x*32+b); } } } } } }
它用于位标志存储，以及用于解析不同的二进制协议字段，其中1字节被分成多个位字段。 这在TCP / IP等协议中广泛使用，直到ASN.1编码，OpenPGP数据包等。