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

Question

我正在学习 C/C++ 编程 &遇到过“位数组”或“位向量”的使用。无法理解他们的目的吗？这是我的疑问 -

1. 它们是否用作布尔标志？
2. 可以使用 int 数组代替吗？ （当然需要更多内存，但是..）
3. 位屏蔽的概念是什么？
4. 如果位掩码是简单的位操作以获得适当的标志，那么如何为它们编程？在 head 中执行此操作以查看与十进制数字相对应的标志是什么，是不是很困难？

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

Q. 您将获得一个包含范围（1 到 100 万）整数的文件。有一些重复，因此缺少一些数字。寻找寻找失踪者的最快方法 数字？

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

Answer 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

我确信您知道 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 的幂）分配给特定含义，并应用二进制运算来推断它们是否已设置，然后对它们进行操作。

我还应该补充一点，二进制运算在思想上与计算机的底层电子器件很接近。想象一下，如果位字段对应于各种电路的输出（是否承载电流）。通过使用足够多的上述电路的组合，你就可以制造出……一台计算机。

Answer 2

关于位数组的用法：

如果您知道“只有”100 万个数字 - 您可以使用 100 万位的数组。一开始，所有位都为零，每次读取数字时 - 使用该数字作为索引，并将该索引中的位更改为 1（如果它还不是 1）。

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

例如，如果我们只有 0 - 4 之间的数字，则数组的开头将如下所示：0 0 0 0 0。
如果我们读数字：3,2,2
数组看起来像这样：read 3 --> 0 0 0 1 0. 读 3（再次） --> 0 0 0 1 0.读取2 --> 0 0 1 1 0.检查零的索引：0,1,4 - 这些是缺失的数字

顺便说一句，当然你可以使用整数而不是位，但它可能需要（取决于系统）32倍内存

Sivan

Answer 3

位数组或位向量可以作为布尔值数组。通常，布尔变量至少需要一个字节存储，但在位数组/向量中只需要一位。
如果您有大量此类数据，这会很方便，因此可以节省大量内存。

另一种用法是如果您有数字不完全适合标准变量，其大小为 8、16、32 或 64 位。您可以通过这种方式将一个由 4 位、一个 2 位和一个 10 位组成的数字存储到 16 位的位向量中。通常您必须使用 3 个大小为 8,8 和 16 位的变量，因此您只浪费了 50% 的存储空间。

但所有这些用途在业务应用程序中很少使用，在通过pinvoke/interop函数连接驱动程序以及进行低级编程时经常使用。

Answer 4

位向量的位数组用作从位置到某个位值的映射。是的，它与 Bool 数组基本相同，但典型的 Bool 实现是一到四个字节长，并且使用了太多空间。

通过使用字数组和二进制掩码操作以及移位来存储和检索它们，我们可以更有效地存储相同数量的数据（更少的总体内存使用，更少的内存访问，更少的缓存未命中，更少的内存页面交换）。访问各个位的代码仍然非常简单。

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);
                    }
                }
            }
        }
    }
}

Answer 5

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