Go bitset Complement为何需要明确有效长度

我第一次用 Complement() 做可用编号筛选时，最容易误会的一点是：补集并不是“所有没有出现过的非负整数”。在 github.com/bits-and-blooms/bitset 中，Complement 只会在 BitSet 的当前有效长度以内翻转位。长度没有先定义清楚，结果自然会看起来少了一截，或者在后续 Set 扩容后发生变化。

官方地址：https://pkg.go.dev/github.com/bits-and-blooms/bitset

把 Complement 理解成“当前长度范围内的反选”即可：先用 New(length) 定义观察范围，再用 Len、Count 和 Test 解释结果。它不是一个带有无限上界的数学补集。

Complement 翻转的到底是哪一段

这个包把非负整数映射成位。位被设置为 1，表示对应的整数属于集合；没有设置则为 0。关键在于 BitSet 还维护着一个长度概念，Complement 的文档描述是计算“up to length bits”的局部补集。

例如长度为 8 的位图中，位下标范围是 0 到 7。若只设置 1 和 3，补集就是 0、2、4、5、6、7；下标 8 及更大的位不在本次运算的观察范围内。

先用 New 明确补集边界

如果业务要表示“0 到 7 中未占用的编号”，构造时就应该把 8 写出来。下面的示例只演示 API 关系，输出依据官方方法语义推导，重点是观察范围而不是把结果当成无限集合。

package main

import (
    "fmt"

    "github.com/bits-and-blooms/bitset"
)

func main() {
    // 明确业务只观察 0 到 7，共 8 个位置。
    used := bitset.New(8).Set(1).Set(3)

    // Complement 返回长度 8 以内没有被设置的位。
    available := used.Complement()

    // Len 是当前长度，Count 是结果中的 1 的数量，两者回答不同问题。
    fmt.Println("used:", used.String())
    fmt.Println("available:", available.String())
    fmt.Println("length:", available.Len())
    fmt.Println("count:", available.Count())
}

这里的结果应当包含 {0,2,4,5,6,7}，长度仍为 8，Count 为 6。Len() 说明边界，Count() 说明边界内有多少个 1，不能互相替代。

Set 超过原长度时，补集边界也会改变

我在排查“为什么补集突然多出一个编号”时，通常先看最后一次 Set 的下标。BitSet 会扩展到已访问的最大下标之后；因此在 New(8) 上设置下标 10，当前长度至少会来到 11。下一次 Complement 就会在 0 到 10 的范围内翻转，而不是继续停留在 0 到 7。

// 这个例子把一个超出初始范围的编号放进集合，观察长度变化。
used := bitset.New(8).Set(1).Set(3)
fmt.Println("before:", used.Len())

// Set(10) 会让当前 BitSet 的可观察范围扩展到包含下标 10。
used.Set(10)
available := used.Complement()
fmt.Println("after:", used.Len())
fmt.Println("available:", available.String())

这段代码的关键不是某个固定字符串，而是边界变化：下标 10 已经属于集合，补集不会再包含 10；原来 8 和 9 也进入了有效范围，因此它们可能出现在补集中。若业务上限固定为 8，就应该在写入前拒绝或单独处理超界编号。

用 Len、Count 和 Test 复查结果

Complement 返回一个新的 BitSet；在解释它时，建议同时记录三个值。Len 用来确认边界，Count 用来确认翻转后的数量，Test 用来确认某个关键下标是否属于结果。

// 复查边界、数量和一个业务关注位，避免只打印集合字符串。
used := bitset.New(8).Set(1).Set(3)
available := used.Complement()

fmt.Println("range:", available.Len())
fmt.Println("available count:", available.Count())
fmt.Println("zero is available:", available.Test(0))
fmt.Println("one is available:", available.Test(1))

对长度为 8、原集合有两个位的例子，补集数量应为 6。若 Count 不符合这个关系，先检查是否在 Complement 前调用过 Set、Flip 或其他会扩展长度的方法。

三个容易踩坑的边界

还要注意并发边界：官方文档说明同一个 BitSet 通常不能被多个 goroutine 无同步地访问。补集结果要交给其他 goroutine 时，先完成所有写入，再通过 channel 转移所有权，或者使用互斥锁保护读写。

把“有效长度”当成业务契约

如果补集用于分配槽位、权限位或特征集合，我会把容量和 BitSet 分开保存。例如 limit 表示业务允许的范围，BitSet 表示当前状态；每次 Set 前检查 i ，每次取 Complement 后再用 Len 和 Count 做记录。这样即使未来换成别的位图实现，边界也不会隐藏在内部容量里。

// limit 是业务契约，BitSet 只是保存状态；两者不要混为一个概念。
const limit uint = 8
used := bitset.New(limit)

for _, i := range []uint{1, 3} {
    // 超过上限的编号不应悄悄改变补集范围。
    if i >= limit {
        continue
    }
    used.Set(i)
}

available := used.Complement()
fmt.Println("valid range:", limit)
fmt.Println("available:", available.String())

结语：先定范围，再谈补集

Go bitset 的 Complement 没有“少翻了一部分”的问题，它遵守的是局部补集语义：翻转当前长度以内的位。最稳妥的使用顺序是先用 New 明确范围，写入时守住上限，结果出来后用 Len、Count 和 Test 复查。只要把有效长度作为业务契约，空集合、动态扩容和固定容量三种情况就不会混在一起。

相关问题

• Complement 会修改原 BitSet 吗？文档签名返回新的结果对象；需要原对象继续表示已用集合时，应保留原指针并使用返回值。
• 为什么 Len 不是 Count？Len 表示当前位范围，Count 只统计范围内值为 1 的位。
• Set 一个很大的下标有什么风险？位图会按最大下标扩展，过大的输入可能造成很高的内存占用，应先做业务边界检查。