Java BitSet 查找下一个置位索引方法

Java BitSet 的 `nextSetBit()` 方法常被误解为迭代器或自增工具，实则是一个无状态、单次定位的“向高位查找首个置位索引”的纯函数——它从指定起始位置（含）开始扫描，返回第一个值为 `true` 的位索引，找不到则返回 `-1`；错误地用 `i = bs.nextSetBit(i)` 推进会导致死循环或跳位，正确遍历必须写成 `i = bs.nextSetBit(i + 1)` 或采用健壮的 for 循环模式 `for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1))`；该方法在稀疏位图场景下性能优异，广泛适用于权限标记、轻量整数集合及布隆过滤器二次校验等实战需求，但需警惕负索引处理、边界语义（优先用 `length()` 而非 `size()`）、缺失反向查找支持等关键细节。

nextSetBit() 的行为本质是“从某位置开始向后找第一个 1”

nextSetBit() 不是遍历器，也不是迭代函数，它只做一件事：从传入的 fromIndex（含）开始，向高位方向扫描，返回第一个值为 true 的位索引；如果找不到，返回 -1。它不维护内部状态，每次调用都是独立的、从头计算的——这点常被误认为“可续查”，结果写出死循环或跳过位。

常见错误现象：
– 写成 int i = bs.nextSetBit(0); while (i != -1) { ... i = bs.nextSetBit(i); } → i 传进去是已知为 1 的位置，nextSetBit(i) 会从该位开始查，包含自身，所以如果该位是 1，就永远返回 i，死循环。
– 误以为 nextSetBit(5) 会跳过第 5 位去找下一个，实际它检查第 5 位本身是否为 1。

正确用法必须「查完当前位后，从下一位起查」：
– 应该写成 i = bs.nextSetBit(i + 1) 才能推进
– 或更安全地：先查，再更新 i

如何用 nextSetBit() 遍历所有 true 位（带边界防护）

最简健壮遍历模式是：for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1))。这个写法天然规避了 i == -1 后继续调用的风险，也避免了 i 停在末尾导致越界。

使用场景包括：
– 统计稀疏位图中所有激活索引（如权限 ID、事件类型标记）
– 实现轻量级整数集合（替代 HashSet，尤其当值域集中且上限已知）
– 与布隆过滤器配合做二次确认（先过布隆，再用 BitSet 精确查）

注意点：
– nextSetBit() 时间复杂度不是 O(1)，但 JDK 8+ 对底层 word 扫描做了优化，平均接近 O(1)；最坏仍是 O(n/64)，不过实践中几乎感知不到
– 若 BitSet 长度极大（如百亿位），但设置位极少，这种遍历仍高效；若大部分位为 1，不如直接用 stream().toArray()（JDK 12+）或传统 for 循环

为什么不能用 nextSetBit(i) 替代 i++ 来推进循环变量

因为 nextSetBit(i) 返回的是“下一个 1 的位置”，不是“下一个索引”。若中间存在连续 0，它会跳过一大段；若中间无 1，就直接返回 -1 —— 它不保证步进，只保证定位。

容易踩的坑：
– 把它当 i++ 用，导致漏掉非连续 true 位之间的逻辑处理
– 在需要“对每个索引做判断”的场景（比如逐位解码协议字段）错误替换，造成逻辑断层
– 和 length() 混淆：即使 bs.length() == 100，nextSetBit(99) 可能返回 -1（第 99 位是 0），也可能返回 99（是 1），但它绝不会返回 100 或更大值（BitSet 不自动扩容到新 set 位）

性能提示：
– 多次调用 nextSetBit() 比批量获取（如转 long[] 数组再手工 scan）开销略高，但代码简洁性与可读性优势明显
– 如果遍历频次极高（如每毫秒万次），且位图结构稳定，可考虑缓存 toLongArray() 结果并手写 word-level 扫描

nextSetBit() 在负索引、越界、空 BitSet 下的表现

nextSetBit(-1) 是合法调用，等价于 nextSetBit(0)；JDK 明确允许负起始索引，内部会按 Math.max(0, fromIndex) 处理。

边界情况实测行为：
– 空 BitSet（未 set 过任何位）：无论 fromIndex 多大，始终返回 -1
– fromIndex >= bitSet.size()（注意不是 length()）：返回 -1；size() 是分配的位容量，length() 是最高 set 位索引 + 1
– fromIndex 超过 Long.MAX_VALUE？会抛 IllegalArgumentException，但日常完全无需考虑

建议始终用 length() 做上界参考而非 size()，因为：
– length() 是语义长度（“这个 BitSet 有效管到哪”）
– size() 是内存分配量（可能远大于实际需要，尤其经过多次 set(largeIndex) 后）
– 例如：只 set(1000)，length() == 1001，但 size() 可能是 2048（按 word 对齐）

真正容易被忽略的是：没有“前一个 set 位”的对应方法。Java 的 BitSet 没有 prevSetBit()，需要自己倒序扫描或维护反向索引。

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~