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

根据我之前的评论，这里有一个例子，说明如何将8个1位元素打包成一个char物理元素。 我只实现了获取1位元素值的函数，我将函数设置为你（这很容易）。

注意：您可以轻松更改数组元素的类型（unsigned char）并尝试可以容纳更多位的类型（例如unsigned int），并测试它们在速度方面的表现是否更好。 您还可以修改代码以使其处理大于一位的元素。

#include <stdio.h>
#include <limits.h>

unsigned int get_el(unsigned char* array, unsigned int index)
{
    unsigned int bits_per_arr_el = sizeof(unsigned char)*CHAR_BIT;
    unsigned int arr_index = index / bits_per_arr_el;
    unsigned int bit_offset = index % bits_per_arr_el;
    unsigned int bitmask = 1 << bit_offset;
    unsigned int retval;

    // printf("index=%u\n", index);
    // printf("bits_per_arr_el=%u\n", bits_per_arr_el);
    // printf("arr_index=%u\n", arr_index);
    // printf("bit_offset=%u\n", bit_offset);

    retval = array[arr_index] & bitmask ? 1 : 0; // can be simpler if only True/False is needed
    return(retval);
}

#define MAX_SIZE 10
unsigned char bitarray[MAX_SIZE];

int main()
{
    bitarray[1] = 3; // 00000011
    printf("array[7]=%u, array[8]=%u, array[9]=%u, array[10]=%u\n",
            get_el(bitarray, 7),
            get_el(bitarray, 8),
            get_el(bitarray, 9),
            get_el(bitarray,10));

    return 0;
}

输出

array[7]=0, array[8]=1, array[9]=1, array[10]=0

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评论使用数组（unsigned short []） 并定义位掩码

#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/structure-packing/  详细

要存储0到1023之间的值（或者从1到1024，这实际上是相同的，只涉及加/减1），您需要至少10位。

这意味着对于32位（无符号）整数，您可以将3个值打包成30位，这会产生2位无用的填充。

例：

%define ELEMENTS 100

uint32_t myArray[ (ELEMENTS + 2) / 3 ];

void setValue(int n, int value) {
    uint32_t temp;
    uint32_t mask = (1 << 10) - 1;

    if(n >= ELEMENTS) return;
    value--;                        // Convert "1 to 1024" into "0 to 1023"
    temp = myArray[n / 3];
    mask = mask << (n % 3)*10;
    temp = (temp & ~mask) | (value << (n % 3)*10);
    myArray[n / 3] = temp; 
}

int getValue(int n) {
    uint32_t temp;
    uint32_t mask = (1 << 10) - 1;

    if(n >= ELEMENTS) return 0;
    temp = myArray[n / 3];
    temp >>= (n % 3)*10;
    return (temp & ~mask) + 1;
}

您可以使用位域来执行此操作，但获取/设置单个值的代码最终将使用分支（例如 switch( n%3 )）在实践中会慢一些。

删除这2位填充将花费更多的复杂性和更多的开销。例如：

%define ELEMENTS 100

uint32_t myArray[ (ELEMENTS*10 + 31) / 32 ];

int getValue(int n) {
    uint64_t temp;
    uint64_t mask = (1 << 10) - 1;

    if(n >= ELEMENTS) return 0;

    temp = myArray[n*10/32 + 1];
    temp = (temp << 32) | myArray[n*10/32];

    temp >>= (n*10 % 32);

    return (temp & ~mask) + 1;
}

这不能用位域完成。这是存储范围从1到1024的值数组的最节省空间的方法。

如果要存储“布尔数组”或设置标志，它可能很有用。例如，您可以一次初始化或比较多达64个值。

这些宏适用于unsigned char，short，int，long long ...但是如果你只选择一个类型会显着简化（所以你可以使用更安全的静态内联函数）

#define getbit(x,n) x[n/(sizeof(*x)*8)]  &  (typeof(*x))1 << (n&((sizeof(*x)*8)-1)) 
#define setbit(x,n) x[n/(sizeof(*x)*8)] |=  (typeof(*x))1 << (n&((sizeof(*x)*8)-1)) 
#define flpbit(x,n) x[n/(sizeof(*x)*8)] ^=  (typeof(*x))1 << (n&((sizeof(*x)*8)-1)) 
#define clrbit(x,n) x[n/(sizeof(*x)*8)] &= ~( (typeof(*x))1 << (n&((sizeof(*x)*8)-1)) ) 

初始化大量的布尔值你需要做的就是： char cbits[]={0,0xF,0,0xFF};

或者全部为零 char cbits[4]={0};

或者一个int例子： int ibits[]={0xF0F0F0F0,~0};

// 1111000011110000111100001111000011111111111111111111111111111111

如果您只访问一种类型的数组，最好将宏转换为适当的函数，如：

static inline unsigned char getbit(unsigned char *x, unsigned n){ 
  return x[n>>3]  &  1 << (n&7); 
}
//etc... similar for other types and functions from macros above

你也可以通过'|'标记一起比较多个标志并使用'＆'ed mask;但是，当你超过本机类型时，它会变得更复杂一些

对于您的特定实例，您可以通过以下方式初始化为全零：

unsigned char flags[128]={0};

或者全部1：

uint64_t flags[128] = {~0,~0,~0,~0,~0,~0,~0,~0,~0,~0,~0,~0,~0,~0,~0,~0};

您甚至可以使用枚举来命名您的标志

enum{
  WHITE, //0
  RED, //1
  BLUE, //2
  GREEN, //3
  ...
  BLACK //1023
}

if (getbit(flags,WHITE) && getbit(flags,RED) && getbit(flags,BLUE))
  printf("red, white and blue\n");

1）这个问题的正确解决方案是使用比特阵列

这个问题提供了解决方案 具有Struct的位字段。有两种典型的方法可以为位相关问题节省内存空间，另一种方法是使用 位数组。对于问题中的这种特定情况，更好的方法是使用Bit Array（演示如下）。

• 如果在这种情况下就像纯粹独立的位标志一样，那就去吧 为了 位数组 
• 如果存在一组相关位，例如IP地址或控制字定义，那么最好将它们与结构组合，即使用 带有Sturct的位字段

2）仅用于演示位阵列的示例代码

#include<limits.h>
#define BITS_OF_INT (sizeof(int)*CHAR_BIT)  
void SetBit(int A[], int k)
     {
       //Set the bit at the k-th position
       A[k/BITS_OF_INT] |= 1 <<(k%BITS_OF_INT);
     } 
void ClearBit(int A[], int k)
     {
       //RESET the bit at the k-th position
       A[k/BITS_OF_INT] &= ~(1 <<(k%BITS_OF_INT)) ;
     }  
int TestBit(int A[], int k)
     {
       // Return TRUE if bit set    
       return ((A[k/BITS_OF_INT] & (1 <<(k%BITS_OF_INT)))!= 0) ;
     }

#define MAX_SIZE 1024
int main()
{
    int A[MAX_SIZE/BITS_OF_INT];
    int i;
    int pos = 100; // position

    for (i = 0; i < MAX_SIZE/BITS_OF_INT; i++)
        A[i] = 0; 

    SetBit(A, pos);
    if (TestBit(A, pos)){//do something}
    ClearBit(A, pos); 
}

3）此外，这个问题值得讨论的一点是，

如何选择合适的解决方案 “比特阵列” 和 “带字段的位字段”？

以下是有关此主题的一些参考资料。

• 何时在C中使用位域？

• C中可读和可维护的位域