位掩码

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. 挑战

For source code example involving bitmask/bit manipulation, please review: bit_manipulation.cpp | py | java | ml.


To test your understanding about bit manipulation, try our Online Quiz on bitmask topic.


And for more challenging problems involving bitmask/bit manipulation, try the following online judge problems: UVa 11933 - Splitting Numbers and Kattis - bitbybit.


Beyond these simple applications, bitmask frequently used as low-level optimizations in a few advanced algorithms, so get ready when you encounter bitmask as sub-component of the bigger algorithms.