位掩码

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)