位掩码

位运算

说明

用整数的每一位表示一个布尔状态；添加、移除和判断均为 O(1)。

分析

第 i 位可以表示第 i 个功能是否启用、元素是否已选等布尔状态。按位或设置该位，按位清除移除它，按位与检查它。

图解推演

低位从 0 编号，第 2 位权重为 4。空状态 0000 按位或 0100 得到 0100；检查与 0100 的交集非零即为存在；清除使用按位清除而不是减法，重复清除也应保持不变。位号必须处于约定字长内。

查看图表代码

适用前提与边界

一个机器字只能容纳有限个状态；超过字长时要使用多个字或位集合。

示例输入与调用

mask := Add(0, 2)
	fmt.Println(Contains(mask, 2), Contains(Remove(mask, 2), 2))

运行输出

true false

完整 Go 示例

package main

import "fmt"

func Add(mask uint, i uint) uint {
	return mask | 1<<i
}
func Remove(mask uint, i uint) uint {
	return mask &^ (1 << i)
}
func Contains(mask uint, i uint) bool {
	return mask&(1<<i) != 0
}

func main() {
	mask := Add(0, 2)
	fmt.Println(Contains(mask, 2), Contains(Remove(mask, 2), 2))
}