如何使用位域来节省内存？

Question

这是关于ANSI-C(C90).这就是我所知道的:

• 我可以直接告诉编译器我想要一个特定变量的位数.
• 如果我想要1位,其值可以为零或一.
• 或者值为0,1,2,3的2位,依此类推......;

我熟悉语法.

我有关于位域的问题:

• 我想定义一个SET结构.
• 它可以有最多1024个元素(它可以有更少,但最多是1024个元素).
• 集合的域为1到1024.因此元素可以具有任何值1-1024.

我正在尝试为SET创建一个结构,它必须对内存部分尽可能高效.

我试过了:

typedef struct set
{
    unsigned int var: 1;
} SET;
//now define an array of SETS
SET array_of_sets[MAX_SIZE]  //didn't define MAX_SIZE, but no more than 1024 elements in each set.

我知道这不高效; 也许它对我想要的东西甚至不好.这就是为什么我在寻求帮助.

Answer 1

正如在广泛的评论中所指出的那样,使用位字段不是可行的方法.对于包含值1..1024的集合,您只能使用128字节的存储空间.您需要将值N映射到位N-1(因此您可以使用位0..1023).您还需要确定所需的操作.此代码支持'create','destroy','insert','delete'和'in_set'.它不支持迭代集合中的元素; 如果你想要它可以添加.

sets.h

#ifndef SETS_H_INCLUDED
#define SETS_H_INCLUDED

typedef struct Set Set;
enum { MAX_ELEMENTS = 1024 };

extern Set *create(void);
extern void destroy(Set *set);
extern void insert(Set *set, int value);
extern void delete(Set *set, int value);
extern int in_set(Set *set, int value);

#endif /* SETS_H_INCLUDED */

sets.c

#include "sets.h"
#include <assert.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned long Bits;
#define BITS_C(n)  ((Bits)(n))
enum { ARRAY_SIZE = MAX_ELEMENTS / (sizeof(Bits) * CHAR_BIT) };

struct Set
{
     Bits set[ARRAY_SIZE];
};

Set *create(void)
{
    Set *set = malloc(sizeof(*set));
    if (set != 0)
        memset(set, 0, sizeof(*set));
    return set;
}

void destroy(Set *set)
{
    free(set);
}

void insert(Set *set, int value)
{
    assert(value >= 1 && value <= MAX_ELEMENTS);
    value--;  /* 0..1023 */
    int index = value / (sizeof(Bits) * CHAR_BIT);
    int bitnum = value % (sizeof(Bits) * CHAR_BIT);
    Bits mask = BITS_C(1) << bitnum;
    /* printf("I: %d (%d:%d:0x%.2lX)\n", value+1, index, bitnum, mask); */
    set->set[index] |= mask;
}

void delete(Set *set, int value)
{
    assert(value >= 1 && value <= MAX_ELEMENTS);
    value--;  /* 0..1023 */
    int index = value / (sizeof(Bits) * CHAR_BIT);
    int bitnum = value % (sizeof(Bits) * CHAR_BIT);
    Bits mask = BITS_C(1) << bitnum;
    /* printf("D: %d (%d:%d:0x%.2lX)\n", value+1, index, bitnum, mask); */
    set->set[index] &= ~mask;
}

/* C90 does not support <stdbool.h> */
int in_set(Set *set, int value)
{
    assert(value >= 1 && value <= MAX_ELEMENTS);
    value--;  /* 0..1023 */
    int index = value / (sizeof(Bits) * CHAR_BIT);
    int bitnum = value % (sizeof(Bits) * CHAR_BIT);
    Bits mask = BITS_C(1) << bitnum;
    /* printf("T: %d (%d:%d:0x%.2lX) = %d\n", value+1, index, bitnum, mask,
              (set->set[index] & mask) != 0); */
    return (set->set[index] & mask) != 0;
}

#include <stdio.h>

enum { NUMBERS_PER_LINE = 15 };

int main(void)
{
    Set *set = create();
    if (set != 0)
    {
        int i;
        int n = 0;
        for (i = 1; i <= MAX_ELEMENTS; i += 4)
             insert(set, i);
        for (i = 3; i <= MAX_ELEMENTS; i += 6)
             delete(set, i);

        for (i = 1; i <= MAX_ELEMENTS; i++)
        {
             if (in_set(set, i))
             {
                 printf(" %4d", i);
                 if (++n % NUMBERS_PER_LINE == 0)
                 {
                     putchar('\n');
                     n = 0;
                 }
             }
        }
        if (n % NUMBERS_PER_LINE != 0)
            putchar('\n');
        destroy(set);
    }
    return 0;
}

这些函数应该给出系统的前缀,例如set_.该BITS_C宏基于C99及更高版本中INT64_C定义的宏(以及其他相关宏)<stdint.h>,它也不是C90的一部分.

Answer 2

typedef struct set
{
    unsigned short var:10; // uint var:1 will be padded to 32 bits
} SET;                     // ushort var:10 (which is max<=1024) padded to 16 bits

正如 @Jonathan Leffler 所评论的，使用数组（无符号短[]）并定义位掩码

#define bitZer 0x00  //(unsigned)(0 == 0)? true:true;
#define bitOne 0x10  // so from (both inclusive)0-1023 = 1024
...                  // added for clarification  
#define bitTen 0x0A

查看每个元素的位。 http://www.catb.org/esr/structural-packing/ 详细