C/C++ 位数组或位向量
https://stackoverflow.com/questions/4604130
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我正在学习 C/C++ 编程并且遇到过“位数组”或“位向量”的用法。无法理解他们的目的吗？这是我的疑问 -
- 它们用作布尔标志吗？
- 可以一个用吗
int数组代替？（当然更多的记忆，但是..） - 位屏蔽的概念是什么？
- 如果位掩码是简单的位操作以获得适当的标志，那么如何为它们编程？在 head 中执行此操作以查看与十进制数字相对应的标志是什么，是不是很困难？
我正在寻找应用程序，以便我可以更好地理解。对于例如 -
问。 您将获得一个包含范围（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 万位的数组。一开始，所有位都为零，每次读取数字时 - 使用该数字作为索引，并将该索引中的位更改为 1（如果它还不是 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 - 这些是缺失的数字
顺便说一句，当然你可以使用整数而不是位，但它可能需要（取决于系统）32倍的内存
西万
位数组或位向量可以作为 布尔值数组. 。通常，布尔变量至少需要一个字节存储，但在位数组/向量中只需要一位。如果您有大量此类数据，这会很方便，因此可以节省大量内存。
另一种用法是如果你有 不完全符合标准变量的数字 大小为 8、16、32 或 64 位。您可以通过这种方式将一个由 4 位、一个 2 位和一个 10 位组成的数字存储到 16 位的位向量中。通常您必须使用 3 个大小为 8,8 和 16 位的变量，因此您只浪费了 50% 的存储空间。
但所有这些用途在业务应用程序中很少使用，在通过接口连接驱动程序时经常使用 pinvoke/互操作 功能和做事 低级编程.
位向量的位数组用作从位置到某个位值的映射。是的，它与 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);
}
}
}
}
}
}
它用于位标志存储，以及解析不同的二进制协议字段，其中 1 个字节被划分为多个位字段。它广泛用于 TCP/IP、ASN.1 编码、OpenPGP 数据包等协议中。
