数据结构 -- 位域

前言

一个字节有8位，在存储时有些数据并不需要占用一个完整的字节，只需要占用一个或几个二进制位即可。例如开关只有通电和断电两种状态，用 0 和 1 表示足以，也就是用一个二进位。基于这种考虑，C语言提供了『位域』这个数据结构。

1. 位域的定义

在结构体定义时，我们可以指定某个成员变量所占用的二进制位数（Bit），这就是位域。来看下面的例子：

struct bs{
    unsigned int m;
    unsigned short n: 4;
    unsigned char ch: 6;
};

• :后面的数字用来限定成员变量占用的位数，即『位宽』，需要注意的是，位宽不能超过成员数据类型长度。
• 成员m没被限制，为『非位域成员』，根据其类型计算，占用4字节，即32位。
• 成员n和成员ch被限制位数，为『位域成员』，不能再根据数据类型来计算长度，所以分别占用4位、6位的内存。

为什么用unsigned标识？

数据分为signed和unsigned两种类型：
--signed：有符号类型，区分正负，第一位是符号位，0表示正，1表示负。
--unsigned：无符号类型，只有正值。
默认是signed类型，以位域成员n来说，如果不用unsigned来标识，虽然限制位宽为4位，但因为第一位是符号位，区分正负，所以实际最大值为3位。

2. 位域溢出

当限制了成员的位数时，如果给成员赋值超过其位数，则会导致数据溢出。来看下面的例子：

int main(){
   //定义一个含有位域成员的结构体
   struct bs{
        unsigned int m;
        unsigned short n: 4;
        unsigned char ch: 6;
    } a;

    //第一次赋值并输出
    a.m = 0xad;
    a.n = 0xf;
    a.ch = '9';
    printf("第一次输出：a.m = %#x, a.n = %#x, a.ch = %c\n", a.m, a.n, a.ch);

    //第二次赋值并输出
    a.m = 0xabcdef10;
    a.n = 0xab;
    a.ch = 'a';
    printf("第二次输出：a.m = %#x, a.n = %#x, a.ch = %c\n", a.m, a.n, a.ch);

    return 0;
}

上面定义了结构体变量a，包含一个非位域成员m，以及两个位域成员n、ch。分别进行两次赋值并输出，输出结果如下所示：

第一次输出：a.m = 0xad, a.n = 0xf, a.ch = 9
第二次输出：a.m = 0xabcdef10, a.n = 0xb, a.ch = !

第一次赋值的输出结果分析：

• a.m = 0xad：因为0xad只占一个字节，m能完整读写，所以输出为0xad。
• a.n = 0xf：0xf对应二进制为0000 1111，n能完整读写4位，所以输出为0xf。
• a.ch = '9'：字符9的值为57，对应的二进制为0011 1001，ch能完整读写6位，所以输出为字符9。

第二次赋值的输出结果分析：

• a.m = 0xabcdef10：因为m能完整读写4字节，所以输出为 0xabcdef10。
• a.n = 0xab：0xab对应二进制为1010 1011，n的内存只能存后4位，即1011，所以输出为0xb。
• a.ch = 'a'：字符a的值为97，对应的二进制为0110 0001，ch的内存只能存后6位，即10 0001，对应的字符为!，所以输出为字符!。

3. 位域的储存

位域的储存规则如下：

1. 当相邻成员的类型相同时，如果它们的位宽之和小于类型的 sizeof 大小，那么后面的成员紧邻前一个成员存储，直到不能容纳为止；如果它们的位宽之和大于类型的 sizeof 大小，那么后面的成员将从新的存储单元开始，其相对于首位的偏移量为类型大小的整数倍。
2. 当相邻成员的类型不同时，不同的编译器有不同的实现方案，GCC会压缩存储，而 VC/VS 不会。
3. 如果成员之间穿插着非位域成员，那么不会进行压缩。

位域实质上是含有位域成员的结构体，所以除了遵循这个储存规则外，还需要遵循结构体分内存对齐规则，接下来通过如下示例来分析位域的存储逻辑。

示例1：

int main(){

    struct bs{
        unsigned int m: 6;     // (0 - 5)
        unsigned int n: 12;    // (6 -17)
        unsigned int p: 4;     // (18-21)  
    };
   
    //输出位域的内存大小
    printf("bs.size = %d \n", sizeof(struct bs));
    return 0;
}

//输出结果
bs.size = 4 

输出结果分析：

• m：m占用6位内存，作为第一个成员，会在位域内存中0-5的位置存放。
• n：n和m均为int类型，且位宽之和为18，小于32，所以n会紧挨着m存储，存放在位置6-17。
• p：p和n均为int类型，且位宽之和为16，小于32，所以p会紧挨着n存储，存放在位置18-21。

因此，bs总共需要22位内存，即3字节，而根据结构体对齐规则，bs的内存必须为其最大成员类型长度（int）的整数倍，所以最终输出为4字节。

示例2：

int main(){

    struct bs{
        unsigned int m: 22;    // (0 - 21)
        unsigned int n: 12;    // (32 - 45)
        unsigned int p: 22;    // (64  - 85)
    };

    //输出位域的内存大小
    printf("bs.size = %d \n", sizeof(struct bs));
    return 0;
}

//输出结果
bs.size = 12

输出结果分析：

• m：m占用22位内存，作为第一个成员，会在位域内存中0-21的位置存放。
• n：n和m均为int类型，且位宽之和为34，大于32，所以n不能紧挨着m存储，需要偏移到位置32开始存储，最后存放在位置32-45。
• p：p和n均为int类型，且位宽之和为34，大于32，所以p不能紧挨着n存储，需要偏移到位置64开始存储，最后存放在位置64-85。

因此，bs总共需要86位的内存空间，即11字节，而根据结构体对齐规则，bs的内存必须为其最大成员类型长度（int）的整数倍，所以最终输出为12字节。

示例3：

int main(){

    struct bs{
        unsigned int m1: 12;    // (0 - 11)
        unsigned int m2: 8;     // (12 - 19)
        unsigned int x;         // (32 - 63)
        unsigned int y: 4;      // (64 - 67)
        unsigned int z;         // (96 - 127)
        unsigned int n1: 12;    // (128 - 139)
        unsigned int n2: 12;    // (140 - 151)
    };

    //输出位域的内存大小
    printf("bs.size = %d \n", sizeof(struct bs));
    return 0;
}

//输出结果
bs.size = 20

输出结果分析：

• m1：m1占用12位内存，作为第一个成员，会在位域内存中0-11的位置存放。
• m2：m2和m1均为int类型，且位宽之和为20，小于32，因此m2会紧挨着m1存储，存放在位置12-19。
• x：x是非位域成员，不能紧挨着m2存储，需要偏移到位置32的地方开始存储，且x占用4字节内存，所以最后存放在位置32-63。
• y：由于相邻的x是非位域成员，因此不能紧挨着x存储，需要偏移到位置64的地方开始存储，且y占用4位内存，所以最后存放在位置64-67。
• z：z是非位域成员，不能紧挨着y存储，需要偏移到位置96的地方开始存储，且x占用4字节内存，所以最后存放在位置96-127。
• n1：由于相邻的z是非位域成员，因此不能紧挨着z存储，需要偏移到位置128的地方开始存储，且n1占用12位内存，所以最后存放在位置128-139。
• n2：n2和n1均为位域成员，且均为int类型，位宽之和为24，小于32，因此n2会紧挨着n1存储，存放在位置140-151。

因此，bs需要152位的内存，即19字节，经由结构体内存对齐，需要是4字节的倍数，所以最终输出为20字节。

总结

• 位域实质上是含有位域成员的结构体，位域成员限制的位数不能超过其数据类型的长度。
• 当限制了成员的位数时，如果给成员赋值超过其位数，则会导致数据溢出。
• 位域的存储既要遵循位域储存规则，还需要遵循结构体对齐规则。

推荐阅读

1. 数据结构 -- 结构体Struct
2. 数据结构 -- 共用体Union