位掩码
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. 位掩码运算
在此可视化中,我们只是六种使用常数时间的位运算:
- 设置 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. 挑战
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.