位模式

位模式, Bit Pattern —— 我们可以换一个角度看待一个“数”, 它不单纯是存储传统意义上的数据, 也可以是表示了一串的状态信息等.

当我们用二进制的角度去看待一个数, 它拥有的若干比特, 就可以表示若干状态的集合.

比如 uint8_t state = 0b00101101; 它确乎是 45, 但在二进制的角度下来看, 它可以是一个状态集合, 比如假设我们规定

bit 0 -> Visible
bit 1 -> Selected
bit 2 -> Dirty
bit 3 -> Loaded
bit 4 -> Active
bit 5 -> Pending
bit 6 -> Failed
bit 7 -> Reserved

那么它就是一个由 8 个二值状态组成的集合, 每个 bit 位为 0 表示不处于这个状态, 1 表示处于这个状态.

而位运算就是在位模式下我们进行状态等的修改的强力工具.

下面给出一些常见的用法吧(其实用的非常广泛, 好用)

状态操作

假设存在状态

using StateFlags = uint32_t;

constexpr StateFlags Visible = 1u << 0;
constexpr StateFlags Dirty   = 1u << 1;
constexpr StateFlags Loaded  = 1u << 2;

那么很方便的假设我们要创建一个表示 Dirty 的状态的变量, 只需要 1u << 1 就可以表示.

在逻辑上合并两个状态, 也只要简单的 state1 | state2 即可. 经常阅读代码中, 可以看到添加状态会写 flag |= Visible 就是这个道理. (此处也可以使用 enum 然后重载运算符)

而判断一个 flag 是否存在某状态, 也可以稍微简单的写成 if (flag & SomeState)

那么, 有意思点的(略复杂点的), 我们可是使用 flag &= ~Visible 来表示删除一个状态, 从逻辑上来看 —— 我们求得的是状态集合中 Visible 的补集与 flag 与自己的交集, 那么 flag 中有的不必多说, 由于 Visible 本身不在它的补集中, 所以会被排除掉. 当然, 我们把二进制下它们的每一个比特位写出来模拟一遍也可以得到同样的结果.

很经典的 Toggle 语义也可以使用 XOR 来进行实现 —— flag ^= Dirty (翻转了该比特, 可查之前笔记)

这样自由度非常高, 我们布尔代数和集合代数里面的各种内容就得到了生动的体现a ——

对于单个 bit 来说 0 / 1 类似于 False / True, 所以按位 AND / OR / NOT / XOR 可以看成对每一个 bit 独立执行布尔代数. 更进一步, 如果规定每个 bit 表示“某个状态是否属于集合”, 那么整个整数又可以视作一个有限集合.

& -> intersection
| -> union
~ -> complement
^ -> symmetric difference
A & ~B -> difference

多个字段的聚合

我们可以把一个整数拆成若干字段, 借助 mask “拆解”出其中我们要的部分来进行使用.

比如说在 ChikaEngine 中实现的简单 SlotMap, 就是把一个 32-bit 的 Handle 拆成了前 16 bits 表示 Generation, 后 16 bits 表示 index 这样的玩法. 不过更复杂一点也可以看这个项目中实现的 Snowflake 算法.

那我们先以简单点的 SlotMap 的 Handle 作为例子.

Handle 在逻辑上是

struct
{
	uint16_t index;
	uint16_t generation;
};

但是实际上仅被塞进了一个整数中, 所以在进行判断 index 和 generation 都相等的时候仅需要一个 handle1 == handle2 即可. 非常的方便

那么在构造的时候就可以

uint32_t handle =
    (static_cast<uint32_t>(generation) << 16) |
    static_cast<uint32_t>(index);

把 generation 移动到高 16 位, 然后和 index 做合并.

之后在取用的时候也可以方便的 ——

uint16_t index = handle & 0xFFFF;
uint16_t generation = (handle >> 16) & 0xFFFF;

0xFFFF 是一个全部由 1 构成的 16 bits 的数, 那么取 & 的语义是我们舍弃掉 handle 掉高 16bits (因为高位填充 0),

诶, 来个简单的抽象 —— (value >> shift) & mask 先进行偏移来对齐目标, 然后再过滤不要的比特, 就可以取出我们要的那部分比特, 非常的好.

此时构造的 mask —— 0 表示我不需要当前位, 1 表示我要看当前位

常见的小 Trick

去除二进制表达下最低位的 1

uint32_t cleared = x & (x - 1);

只保留最低位的 1

uint32_t lowbit = x & -x;

可以自己列一下 bit 然后进行一个推的导