位掩码

1. Introduction

位掩码 (Bitmask) 提供了一种有效的方法来处理一小组以32或64位有符号十进制整数形式存储却以长度32/64的字符串来解读的布尔值。
通过使用位运算,可以检查布尔值的每一位是开还是关。 它可以用于各种算法,例如旅行商问题的动态编程解决方案,以加速(小型的)基于集合的关键操作。

2. 可视化

在这里查看位掩码的数据结构及运算的可视化!
最上面一行展示了以第 0 位为最右位的整数 S 中各位 (bit) 的索引。注意我们使用16进制符号 A/B/../E 来表示第 10/11/../14 位。
第二行表示了整数 S 中的各位 (bit)。在实际应用中,S 通常是32位的有符号整数(例如C++和大多数其他语言中的 int 类型)。有时 S 是一个64位的有符号整数(如C++中的 long long 类型)。在此可视化中,我们将 S 限定为16位的有符号整数。
第三行表示了将会在位运算中用在 S 上的位掩码的各个位 (bit)。
最后一行表示结果。

3. 位掩码运算

在此可视化中,我们只是六种使用常数时间的位运算:
  1. 设置 S 的值
  2. 将第 j 位设为 on
  3. 判断第 j 位的值
  4. 将第 j 位设为 off
  5. 对第 j 位取反
  6. 最低有效位

3-1. 设置 S 的值

我们可以输入一个在 [0..32767 (215-1)] 区间内的小整数,然后可视化其二进制的形式。
或者我们也可以随机选一个在 [0..32767] 内的整数,或二进制为 '100...0' 的 2n,或二进制为 '11...1' 的 2n-1。

3-2. 将第 j 位设为 on

我们可以输入第 j 位的索引来将其设为 on。
索引从 0 开始,但是从最右边的位开始数的(见上)。
位运算比较简单:S OR (1 << j)
将一个已经是 on 的位设为 on 不改变任何东西。

3-3. 判断第 j 位的值

我们可以输入第 j 位的索引来判断其状态(on 或 off)。
索引从 0 开始,但是从最右边的位开始数的(见上)。
位运算比较简单:S AND (1 << j)

3-4. 将第 j 位设为 off

我们可以输入第 j 位的索引来将其设为 off。
索引从 0 开始,但是从最右边的位开始数的(见上)。
位运算比较简单:S AND ~(1 << j)
将一个已经是 off 的位设为 off 不改变任何东西。

3-5. 对第 j 位取反

我们可以输入要第 j 位的索引来对其取反(on → off 或 off → on)。
索引从 0 开始,但是从最右边的位开始数的(见上)。
位运算比较简单:S XOR (1 << j)

3-6. 最低有效位

这个运算不需要输入。它只是一个找到 S 中最右边的值为 on 的位的特殊运算。
位运算比较简单:S AND (-S)
注意在补码中,-S = NOT(S)+1

4. 挑战

如果您需要位掩码/位操作的示例源代码,请看:bit_manipulation.cpp | py | java | ml


如需测试您对位操作的理解,可以试试 Online Quiz on bitmask topic


如果您想要关于位掩码/位操作的更有挑战性的问题,试试这里的在线题目:UVa 11933 - Splitting NumbersKattis - bitbybit


除了这些简单的应用,位掩码还常常在高级算法中作为低级优化出现,所以您需要做好在更大的问题中碰到位掩码组件的心理准备。