位域简介
brealid
2020-02-02 17:39:21
[在 cnblogs 博客里阅读](https://www.cnblogs.com/hkxadpall/p/introduction-BitField.html)
提供一种冷门奇怪的语法：**位域定义**。
引入：
> 有些信息在存储时，并不需要占用一个完整的字节， 而只需占几个或一个二进制位。例如在存放一个开关量时，只有0和1 两种状态， 用一位二进位即可。为了节省存储空间，并使处理简便，Ｃ语言又提供了一种数据结构，称为“位域”或“位段”。所谓“位域”是把一个字节中的二进位划分为几 个不同的区域，并说明每个区域的位数。每个域有一个域名，允许在程序中按域名进行操作。 这样就可以把几个不同的对象用一个字节的二进制位域来表示。
> ——摘自 csdn博客 sty124578 [⤴$\!^{_1}$](https://blog.csdn.net/sty124578/article/details/79456405)
本文主要讲解了：
```menu
- 位域的使用
- 定义位域
- 位域运算特点
- 位域定义有什么用
- 搞大工程
- 处理模形如 $2^p(p\texttt{ 为整数且大于 }0)$ 的数的运算
- 位域在 OI 中的应用
- P2033 Chessboard Dance
```
先提供效果代码
```cpp
struct test1 {
unsigned a:2;
};
```
# 位域的使用
## 定义位域
### 例 1
```cpp
struct test1 {
unsigned a:2;
};
```
如上，对于该结构体，在内存中是这样的（一格 = 一位）：
```memory
bit|1|2|3|4|5|6|7|8|
| a | | | | | | |
```
### 例 2
```cpp
struct test2 {
unsigned a:3;
int b:1;
int :2;
unsigned d:2;
};
```
对应在内存中的情况：
```memory
bit|1|2|3|4|5|6|7|8|
| a |b| | d |
^^^
空位不存储有用值
```
### 例 3
```cpp
struct test2 {
unsigned a:3;
int b:1;
int :0;
long long d:8;
};
```
对应在内存中的情况：
```memory
----------------------------------------------
[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. 这个东西冒号后面的数字不能超过类型本身的大小。如：
```cpp
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$ 定义如下：
```cpp
struct T {
unsigned a : 3;
unsigned b : 3;
unsigned c : 3;
int d : 3;
int e : 3;
int f : 3;
};
```
## 例 1
```example
// 已知 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
```example
// 已知 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}$](https://bbs.csdn.net/topics/220005181)
## 处理模形如 $2^p(p\texttt{ 为整数且大于 }0)$ 的数的运算
比如，有一次你需要存储一个整数 $a$，且 $0\le a<8$
$a$ 会有可能加、减、乘一个数，得到的结果仍在 $0\le a<8$ 内，即在 $\bmod\ 2^3$ 意义下运算。
那么用位域是个不错的选择。
```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年. 清华大学出版社.