位掩码
1. Introduction
位掩码提供了一种有效的方式来操作存储为32位（或64位）有符号整数的小布尔集合，但以短32位（或64位）字符字符串的形式解释。
通过使用位运算，可以轻松快速地检查整数的每个位，打开（或关闭）它们。它可以用于各种算法，例如旅行商问题的动态规划解决方案，以加速关键（小）集合操作。
2. 可视化
上面显示了位掩码数据结构及其操作的可视化。
顶部行描述了输入整数 S 的位索引，从最右边的第 0 位开始。请注意，我们使用 1 位十六进制表示法 A/B/../E 来表示第 10/11/../14 位。
第二行描述了输入整数 S 的位。在实际应用中，这通常是一个 32 位有符号整数（例如 C++/大多数其他编程语言中的 int）。有时，这是一个 64 位有符号整数（例如 C++ 中的 long long）。对于此可视化，我们将 S 限制为 16 位有符号整数。
第三行描述了将应用于 S 的 （位）掩码 的位以及相关的按位操作。
最后一行描述了结果。
3. 位掩码运算
在此可视化中，我们只是六种使用常数时间的位运算：
- 设置 S 的值
- 将第 j 位设为 on
- 判断第 j 位的值
- 将第 j 位设为 off
- 对第 j 位取反
- 最低有效位
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) 。
4. 挑战
有关位掩码/位操作的源代码示例，请查看：bit_manipulation.cpp | py | java | ml。
要测试您对位操作的理解，请尝试我们的位掩码主题的在线测验。
而对于涉及位掩码/位操作的更具挑战性的问题，请尝试以下在线评测问题：UVa 11933 - 分割数字 和 Kattis - bitbybit。
除了这些简单的应用之外，位掩码还经常用作一些高级算法中的低级优化，所以当您在更大的算法中遇到位掩码时，请做好准备。