C/C++ 位数组或位向量

Question

我正在学习C/C++编程，遇到了“位数组”或“位向量”的用法。我不理解它们的目的是什么？以下是我的疑问-

1. 它们用作布尔标志吗？
2. 可以使用int数组代替吗？（当然会更消耗内存，但是...）
3. 什么是“位掩码”概念？
4. 如果位掩码是一种简单的位操作，用于获取适当的标志，那么如何为它们编写程序？与十进制数字相比，在头脑中执行此操作以查看标志是否有困难？

我正在寻找应用程序，以便更好地理解。例如 -

问题.给定一个包含1到100万范围内的整数的文件。有一些重复项，因此缺少一些数字。找到查找缺失数字的最快方法？

对于上述问题，我已经阅读了一些解决方案，告诉我使用位数组。如何在位中存储每个整数？

- Srikar Appalaraju

---

顺便提一下，这是C/C++无法使用的一个领域。C++有位向量(bit vectors)，而C没有。在C中，你需要自己编写。请养成将C/C++区分为C或C++的习惯。 - Thomas Matthews

Answer 1

我认为你在数组和数字之间搞混了，特别是对于操作二进制数的含义。

我将通过示例来说明。假设您有一些错误消息，并且想要从函数的返回值中返回它们。现在，您可能会将错误标记为1、2、3、4...这在您的脑海中很有意义，但是如果只给出一个数字，如何确定发生了哪些错误呢？

现在，尝试将错误标记为1、2、4、8、16...即二的递增幂。为什么这样做有效呢？因为当您使用基数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 的幂）表示特定含义，并应用二进制操作来推断它们是否设置，然后对其进行操作。

我还应补充说明，二进制操作与计算机的基础电子学思想密切相关。想象一下，如果比特字段对应于各种电路的输出（传递电流或不传递电流），通过使用足够多的这些电路组合，您可以制造出一台计算机。

- user257111

Answer 2

关于使用比特数组的用法：

如果你知道只有“一百万”个数字-则使用一个由一百万个比特组成的数组。一开始所有比特都为零，每次读取一个数时，将该数字作为索引并将该索引处的位更改为一（如果尚未为一）。

读取所有数字后-缺失的数字是数组中零的索引。

例如，如果我们只有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倍的内存（取决于系统）。

Sivan

- SivGo

---

“一开始，所有的位都将是零”在某种程度上触动了我。 - Frerich Raabe

所以基本上，位数组是存储位（而不是 int 或 char 数组）的数据结构。这意味着，位数组只能在需要开关（或标志）类型应用的地方使用。 - Srikar Appalaraju

是的，唯一的区别就是大小。但是，我只会在想要节省内存或需要将其存储在固定大小空间（如嵌入式寄存器\变量，如int\特定地址等）时使用它。 - SivGo

Answer 3

位向量是一种将位置映射到某个位值的数据结构。虽然它与布尔数组基本相同，但典型的布尔实现长度为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);
                    }
                }
            }
        }
    }
}

- kriss

Answer 4

位数组或位向量可以被看作是一个布尔值数组。通常，一个布尔变量需要至少一个字节的存储空间，但在位数组/向量中只需要一个比特位。如果您有大量这样的数据，这将非常方便，因为您可以节省大量内存。

另一个用途是当您有一些数字不能完全适合标准变量大小（8、16、32或64位）时。您可以使用16位的位向量来存储一个由4位、2位和10位组成的数字。通常情况下，您需要使用3个分别为8、8和16位大小的变量，因此您只浪费了50%的存储空间。

但是所有这些用途在业务应用程序中都很少使用，它们通常在通过pinvoke/interop函数接口驱动程序和进行低级编程时使用。

- codymanix

Answer 5

这是用于存储位标志的，以及用于解析不同的二进制协议字段，其中1个字节被分成多个位字段。这在诸如TCP/IP、ASN.1编码、OpenPGP数据包等协议中广泛使用。

- Nickolay Olshevsky