特别提醒：Python 的同学实现位运算的题目需要特别注意，需要自己去手动处理溢出和符号扩展等问题，比如：
(n << shift_amount) & 0xFFFFFFFF（Python 溢出会自动升位：）
位图原理
其实就是用 bit 组成的数组来存放值，用 bit 状态 1、0 代表存在、不存在，取值和存值操作都用位运算
- 限制是必须为连续范围且不能过大（一开始就会申请这么大的空间）
- 好处是极大的节省空间，因为 1 个数字只占用 1 个 bit 的空间
位图的实现
package main
import (
"fmt"
"math/rand"
"unsafe"
)
const (
INT_BIT_COUNT = int(unsafe.Sizeof(int(0))) * 8 // int 占的位数
MAXN = 10000
TEST_TIMES = 100000
)
var emptyStruct = struct{}{}
func main() {
bitSet := NewBitset(MAXN)
hashSet := make(map[int]struct{}, MAXN)
for i := 0; i < TEST_TIMES; i++ {
num := rand.Intn(MAXN)
decide := rand.Intn(3)
switch decide {
case 0:
bitSet.Add(num)
hashSet[num] = emptyStruct
case 1:
bitSet.Remove(num)
delete(hashSet, num)
case 2:
bitSet.Reverse(num)
if _, has := hashSet[num]; has {
delete(hashSet, num)
} else {
hashSet[num] = emptyStruct
}
}
}
for i := 0; i < MAXN; i++ {
if _, has := hashSet[i]; has != bitSet.Contains(i) {
panic("error")
}
}
fmt.Println("success")
}
// 位图
// 使用时 num 不要超过初始化的大小
type Bitset []int
// n个数字: [0, n)
func NewBitset(n int) Bitset {
// a / b 想向上取整，可以写成: (a+b-1) / b
// 前提是 a 和 b 都是非负数
return make(Bitset, (n+INT_BIT_COUNT-1)/INT_BIT_COUNT)
}
// 把 num 加入位图
func (b Bitset) Add(num int) {
b[num/INT_BIT_COUNT] |= 1 << (num % INT_BIT_COUNT)
}
// 把 num 从位图中删除
func (b Bitset) Remove(num int) {
b[num/INT_BIT_COUNT] &^= 1 << (num % INT_BIT_COUNT)
}
// 如果位图里没有 num，就加入
// 如果位图里有 num，就删除
func (b Bitset) Reverse(num int) {
b[num/INT_BIT_COUNT] ^= 1 << (num % INT_BIT_COUNT)
}
// 查询 num 是否在位图中
func (b Bitset) Contains(num int) bool {
return b[num/INT_BIT_COUNT]&(1<<(num%INT_BIT_COUNT)) != 0
}采用对数器验证，当你找不到测试链接的时候就用对数器验证，而且对数器验证更稳妥、更能练习 debug 能力
找到了一个相关测试：2166.设计位集
type Bitset struct {
data []uint32
size int // 位图大小
count int // 1 的数量
flipped bool // 是否翻转
}
// 用 size 个位初始化 Bitset ，所有位都是 0
func Constructor(size int) Bitset {
return Bitset{
data: make([]uint32, (size+31)/32),
size: size,
count: 0,
flipped: false,
}
}
// 将下标为 idx 的位上的值更新为 1 。如果值已经是 1 ，则不会发生任何改变
func (this *Bitset) Fix(idx int) {
if !this.Has(idx) {
this.count++
this.Reverse(idx)
}
}
// 将下标为 idx 的位上的值更新为 0 。如果值已经是 0 ，则不会发生任何改变
func (this *Bitset) Unfix(idx int) {
if this.Has(idx) {
this.count--
this.Reverse(idx)
}
}
// 翻转 Bitset 中每一位上的值。换句话说，所有值为 0 的位将会变成 1 ，反之亦然
func (this *Bitset) Flip() {
this.flipped = !this.flipped
this.count = this.size - this.count
}
// 第 idx 位是否为 1
func (this *Bitset) Has(idx int) bool {
bit := this.data[idx/32] & (1 << (idx % 32))
if this.flipped {
return bit == 0
}
return bit != 0
}
// 翻转 idx 位上的值。换句话说，所有值为 0 的位将会变成 1 ，反之亦然
func (this *Bitset) Reverse(idx int) {
this.data[idx/32] ^= 1 << (idx % 32)
}
// 检查 Bitset 中每一位的值是否都是 1
func (this *Bitset) All() bool {
return this.count == this.size
}
// 检查 Bitset 中是否至少一位的值是 1
func (this *Bitset) One() bool {
return this.count > 0
}
// 返回 Bitset 中值为 1 的位的总数
func (this *Bitset) Count() int {
return this.count
}
// 返回 Bitset 的当前组成情况
// 注意，在结果字符串中，第 i 个下标处的字符应该与 Bitset 中的第 i 位一致
func (this *Bitset) ToString() string {
var (
builder strings.Builder
status byte
)
for i := 0; i < this.size; i++ {
status = byte((this.data[i/32] >> (i % 32)) & 1)
if this.flipped {
status ^= 1
}
builder.WriteByte('0' + status)
}
return builder.String()
}添加 flipped 变量使得 Flip() 时间复杂度降为 O(1)，而不用遍历整个位图；添加 count 变量使得 All()、One()、Count() 时间复杂度降为 O(1)，而不用遍历整个位图，非常巧妙
备注
位图的后续扩展（如：布隆过滤器、资源限制类题目），将在【扩展】课程里进一步讲述