C中的内存高效标志数组

Question

我需要在内存中存储一个非常长的数组。每个数组项只是一个标记TRUE/FALSE（0/1）。因为我需要它非常节省内存，所以我考虑实现它作为掩码位的方式，放在unsigned char region之上。每个内存中的char应该至少给我8个标记位。我已经实现了以下函数：

static SIZE = 8; /* 8 bits = 1 byte = 1 char */

/* creates and initializes the array for N elements */
unsigned char *new_bit_array(long n) {
    int extra = (n % SIZE) ? 1 : 0;
    size_t ms = ((n / SIZE)+extra) * sizeof(unsigned char);
    unsigned char *p = malloc(ms);
    memset(p,0xFF,ms);
    return p;
}

/* mask setter for nth bit of a char, call by function bit_array_set*/
char bit_mask_set(short nbit,short value) {    
    if (value)
        return  0xFF;
    if (nbit == 0) 
        return 0x7F;
    else if (nbit == 1)
        return 0xBF;
    else if (nbit == 2) 
        return 0xDF;
    else if (nbit == 3) 
        return 0xEF;
    else if (nbit == 4) 
        return 0xF7;
    else if (nbit == 5) 
        return 0xFB;
    else if (nbit == 6) 
        return 0xFD;
    else if (nbit == 7) 
        return 0xFE;
    return 0xFF;
}

/* mask setter for nth element of the array */
void bit_array_set(unsigned char *p,long i,int value) {
    p[i/] &= bit_mask_set(i % SIZE,value);
}

/* mask getter for nth bit of a char, call by function bit_array_get */
char bit_mask_get(short nbit) {
    if (nbit == 0) 
        return 0x80;
    else if (nbit == 1)
        return 0x40;
    else if (nbit == 2) 
        return 0x20;
    else if (nbit == 3) 
        return 0x10;
    else if (nbit == 4) 
        return 0x08;
    else if (nbit == 5) 
        return 0x04;
    else if (nbit == 6) 
        return 0x02;
    else if (nbit == 7) 
        return 0x01;
    return 0x00;
}

/* mask getter for nth element of the array */
short bit_array_get(unsigned char *p,long i) {
    return p[i/SIZE] & bit_mask_get(i % SIZE) ? 1 : 0;
}

这段代码可以正常工作，但我的问题是是否在C语言或任何广泛使用的库中（如glib）有任何内置功能提供相同的功能？

... 还有没有更好的实现bit_mask_get和bit_mask_set的方法，7个分支IF看起来很丑陋。对于这段代码的任何其他评论也非常欢迎。

- Manuel Salvadores

---

这就是 switch 语句的用途。 - user229044

我以前有一个 switch 语句，老实说，它并没有对代码产生太大的改变。基本上还是一样的东西。 - Manuel Salvadores

0xff ^ (1 << (7-nbit)) 可以消除 bit_mask_set 中的 if-else 语句。 - user786653

“非常长”是多长时间？ - wnoise

Answer 1

您可以更简单地完成它：

unsigned char flag_bitmask[MAX_FLAGS];

void setFlag( int flag) {
    flag_bitmask[flag / 8] |= (1 << (flag % 8) );
}

char isFlagSet(int flag) {
    return flag_bitmask[flag / 8] & (1 << (flag % 8) );
}

void unSetFlag(int flag) {
    flag_bitmask[flag / 8] &= ~(1 << (flag % 8) );
}

我经常使用它，你可以传递 flag_bitmask 数组，而不是将其作为全局变量使用。

- MByD

---

我知道有一种简洁的方法来做这件事。好答案（+1） - Manuel Salvadores

如果选择unsigned int替代char，性能会有所变化吗？ - rph

@rkioji - 在大多数情况下并不是这样的，有些平台可能会有差异，但两种方式都可以。我使用无符号字符作为最小可用单元，并且它没有字节序混淆。 - MByD

Answer 2

您可以使用来自的宏CHAR_BIT替换SIZE常量，它们的作用相同。

在new_bit_array函数中，您可以使用(unsigned char) ~0替换0xFF，它不依赖于char中的位数。尽管通过使用而不是malloc将内存初始化为零位可能更容易。

在bit_masK_get中，您可以使用以下内容替换主体：

return 1 << nbit;

然后同样将bit_mask_set替换为:

return (!!value) << nbit;

这些可能将位数与您的不同，但只要它们彼此之间保持一致，就不会产生影响。

- user25148

Answer 3

您可以在结构体中使用位域。您可以拥有以下结构体的数组：

struct bitflags {
    unsigned char f0:1;
    unsigned char f1:1;
    unsigned char f2:1;
    unsigned char f3:1;
    unsigned char f4:1;
    unsigned char f5:1;
    unsigned char f6:1;
    unsigned char f7:1;
};

struct bitflags many_flags[9001];
many_flags[0].f0 = 1;

- Vinicius Kamakura

---

这不会是内存高效的。如果我需要像 1000e6 元素那样多的话，那么我需要 malloc 1000e6/8 指向结构体 bitflags 的指针。指针在内存上是昂贵的。 - Manuel Salvadores

该结构的大小为1字节。这种方法的一个优点是，您可以让编译器确定如何读取和写入特定的位。如果机器语言更好，它可以使用机器的汇编，并且可能比您更好地进行优化。 - Vinicius Kamakura

这其实是真的。如果你在一个连续的内存空间中拥有它，那么就不需要指针，强制转换就可以正常工作。我收回之前的话，这实际上是内存高效的。好答案，干杯（+1）。 - Manuel Salvadores