我正在学习 C/C++ 编程，并且遇到过“位数组”或“位向量”的用法。无法理解他们的目的？这是我的疑问-
int数组吗？（当然更多的记忆，但是..）我正在寻找应用程序，以便我可以更好地理解。例如 -
问：给你一个文件，其中包含范围（1 到 100 万）内的整数。有一些重复，因此缺少一些数字。找到查找缺失数字的最快方法？
对于上述问题，我已经阅读了告诉我使用位数组的解决方案。如何存储每个整数？
我认为您对数组和数字感到困惑，特别是操纵二进制数的含义。
我将通过例子来解决这个问题。假设您有许多错误消息，并且希望将它们作为函数的返回值返回。现在，您可以将错误标记为 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
我确定您知道 and 是如何工作的，或者可以从上面推断出它 - 以数字方式工作，如果任何两个数字都是 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 的幂）分配给特定含义，并应用二进制运算来推断它们是否已设置，然后对它们进行操作。
我还应该补充一点，二进制操作在概念上与计算机的底层电子设备很接近。想象一下，如果位域对应于各种电路的输出（载流与否）。通过使用足够多的上述电路组合，你就可以制造出……一台计算机。
关于位数组的用法：
如果你知道“只有”100 万个数字 - 你使用一个 100 万位的数组。一开始，所有位都将为零，每次您读取一个数字时 - 使用此数字作为索引并将此索引中的位更改为一（如果它还不是一）。
读取所有数字后 - 缺失的数字是数组中零的索引。
例如，如果我们只有 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 - 这些是缺失的数字
顺便说一句，当然您可以使用整数而不是位，但它可能需要（取决于系统）32 倍内存
西万
位向量的位数组用作从位置到某个位值的映射。是的，它基本上与 Bool 数组相同，但典型的 Bool 实现是 1 到 4 个字节长，并且占用了太多空间。
我们可以通过使用单词数组和二进制掩码操作以及转移来存储和检索它们来更有效地存储相同数量的数据（使用更少的整体内存，更少的内存访问，更少的缓存未命中，更少的内存页面交换）。访问各个位的代码仍然非常简单。
C 语言中还内置了一些位字段支持（你写的东西就像int i:1;说“只消耗一位”），但它不适用于数组，并且你对整体结果的控制较少（实现细节取决于编译器和对齐问题）。
以下是回答您的“搜索缺失号码”问题的一种可能方式。我将 int 大小固定为 32 位以保持简单，但可以使用 sizeof(int) 编写它以使其可移植。并且（取决于编译器和目标处理器）代码只能使用>> 5代替/ 32和& 31代替来更快% 32，但这只是为了给出想法。
#include <stdio.h>
#include <errno.h>
#include <stdint.h>
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);
}
}
}
}
}
}
位数组或位向量可以作为一个布尔值数组。通常布尔变量需要至少一个字节存储，但在位数组/向量中只需要一位。如果您有大量此类数据，这会很方便，因此您可以节省大量内存。
另一种用法是，如果您的数字不完全适合8、16、32 或 64 位大小的标准变量。您可以通过这种方式将一个由 4 位、一个 2 位和一个 10 位组成的数字存储到 16 位的位向量中。通常您必须使用 3 个大小为 8,8 和 16 位的变量，因此您只浪费了 50% 的存储空间。
但是所有这些用途都很少用于业务应用程序，通常在通过pinvoke/interop功能连接驱动程序和进行低级编程时使用。
这用于位标志存储，以及用于解析不同的二进制协议字段，其中 1 个字节被划分为多个位字段。这在 TCP/IP 等协议中被广泛使用，最高可达 ASN.1 编码、OpenPGP 数据包等。