在 cnblogs 博客里阅读

提供一种冷门奇怪的语法：位域定义。

引入：

有些信息在存储时，并不需要占用一个完整的字节， 而只需占几个或一个二进制位。例如在存放一个开关量时，只有0和1 两种状态， 用一位二进位即可。为了节省存储空间，并使处理简便，Ｃ语言又提供了一种数据结构，称为“位域”或“位段”。所谓“位域”是把一个字节中的二进位划分为几 个不同的区域，并说明每个区域的位数。每个域有一个域名，允许在程序中按域名进行操作。 这样就可以把几个不同的对象用一个字节的二进制位域来表示。
——摘自 csdn博客 sty124578 ⤴\!^{_1}

本文主要讲解了：

- 位域的使用
    - 定义位域
    - 位域运算特点
- 位域定义有什么用
    - 搞大工程
    - 处理模形如 $2^p(p\texttt{ 为整数且大于 }0)$ 的数的运算
- 位域在 OI 中的应用
    - P2033 Chessboard Dance

先提供效果代码

struct test1 {
    unsigned a:2;
};

位域的使用

定义位域

例 1

struct test1 {
    unsigned a:2;
};

如上，对于该结构体，在内存中是这样的（一格 = 一位）：

bit|1|2|3|4|5|6|7|8|
   | a | | | | | | | 

例 2

struct test2 {
    unsigned a:3;
    int b:1;
    int :2;
    unsigned d:2;
};

对应在内存中的情况：

bit|1|2|3|4|5|6|7|8|
   |  a  |b|   | d | 
            ^^^
       空位不存储有用值

例 3

struct test2 {
    unsigned a:3;
    int b:1;
    int :0;
    long long d:8;
};

对应在内存中的情况：

----------------------------------------------
[Byte 1] bit|1|2|3|4|5|6|7|8|
            |  a  |b|       | 
                     ^^^^^^^
            :0表示这个字节后续的位全部舍弃
----------------------------------------------
[Byte 2] bit|1|2|3|4|5|6|7|8|
            |       d       | 
----------------------------------------------

额外说明

1. 这个东西冒号后面的数字不能超过类型本身的大小。如：

   struct test3 {
   short a:17;   // 不合法，short 本身占 16 个位
   int b:17;     // 合法
   };

2. 这个东西不能定义数组
3. 这个东西不能单独定义，需要在 struct 里面定义
4. 实际上所有整形类数据（如 short, long long, char 等）都是可以声明为位段成员的。
5. Q: 既然一个用位域定义的变量大小已经确定，那么前面的变量类型又有什么用？
   A: 变量类型表示这个变量在运算时的类型。

位域运算特点

运算结果自动上溢。
以下 a,b,c,d,e,f 定义如下：

struct T {
    unsigned a : 3;
    unsigned b : 3;
    unsigned c : 3;
    int d : 3;
    int e : 3;
    int f : 3;
};

例 1

// 已知 a = 3, b = 6, 计算 c = a + b
运算过程
    bit | 4 | 3 | 2 | 1 |
    ----+---+---+---+---+
      a |   | 0 | 1 | 1 |
    + b |   | 1 | 1 | 0 | 
    =   | 1 | 0 | 0 | 1 |
      c |   | 0 | 0 | 1 |
// 第四 bit 值上溢，最终运算结果：c = 1

例 2

// 已知 d = 3, e = 2, 计算 f = d + e
运算过程
        正负位
    bit | 3 | 2 | 1 |
    ----+---+---+---+
      d | 0 | 1 | 1 |
    + e | 0 | 1 | 0 | 
    = f | 1 | 0 | 1 |
// 虽然运算结果没有上溢，但由于 int 的特性，这里 c 的最终结果非 5 而是 -3

位域定义有什么用

搞大工程

搞大工程时，一般会比较注重内存的节约。

例： 如果有两个 unsigned 型的数 a,b，a 保证在使用中小于 2^5，b 保证在使用中小于 2^3。那么使用两个 unsigned short 需要 2 个字节，而使用位域只需要一个字节，节约了空间。

不过，引用一段来自 csdn 论坛的话：

位域是只能用于结构体中，其目的是为了牺牲时间来节省空间，这在早年内存空间少时有意义，现在一般都是牺牲空间来节省时间，因此使用位域不是一个好主意。——arong1234 ⤴\!^{_2}

处理模形如 2^p(p\texttt{ 为整数且大于 }0) 的数的运算

比如，有一次你需要存储一个整数 a，且 0\le a<8

那么用位域是个不错的选择。 ```cpp // 定义 struct number_save { unsigned int a : 3; } num; // 使用 num.a += someNumber; // 无需写模运算即可取余（%8），自动溢出忽略大位上的值 ``` 什么？你觉得没什么用？ 这可以节省一点点字符呀……而且很方便不是吗…… 至少你还可以用来装逼啊…… 什么？你说没有题目会用到“模形如 $2^p(p\texttt{ 为整数且大于 }0)$ 的数”？ 例子马上就来。 # 位域在 OI 中的应用 ## P2033 Chessboard Dance 这里处理转向，使用位域将会非常方便。 首先定义移动用数组 ```cpp const int xx[] = {1, 0, -1, 0}, yy[] = {0, -1, 0, 1}; ``` 注意到如果这样写， - $(xx[0],yy[0])$就对应向下 - $(xx[1],yy[1])$就对应向左 - $(xx[2],yy[2])$就对应向上 - $(xx[3],yy[3])$就对应向右 然后考虑到 4 种情况，方向值 ``dir`` 是在 $\bmod\ 2^2$ 意义下的。 所以定义 ```cpp struct pos { int x, y; uint8 dir : 2; void turn(char ch) { switch (ch) { case 'l' : dir--; break; // left case 'r' : dir++; break; // right case 'b' : dir ^= 2; break; // back } } }; ``` 注意到 ``turn`` 函数里，我没有使用模运算，而是直接加，减。（对于 ``turn back`` 操作，``+2/-2`` 在 $\bmod\ 2^2$ 意义下只需要改变第 2 个 bit 的值即可，所以对于 ``dir ^= 2`` 请感性理解） [AC Code](/paste/dxt4tpng) # 后记 这个东西在 $OI$ 之中或许没什么很大的应用，内存上的优势也因为不能定义数组而微乎其微，连自动溢出的功能用处似乎也不大。 写这篇博客的初衷其实是：在写 P2033 时发现使用位域十分的简洁，所以想跟大家分享一下。 或许读者终其一生都不会使用位域，但多了解一点总是好的。 # 参考资料 1. 位域的定义和使用 by Unix探索之旅 https://blog.csdn.net/sty124578/article/details/79456405 2. 关于位域的问题，想搞个数组，不知道怎么弄 asked by wxbfly answered by arong1234 https://bbs.csdn.net/topics/220005181 3. 谭浩强《c程序设计》（第四版）2010年. 清华大学出版社.