Day 58: std.bit_bag模块：位袋操作

1. 引言：动态位集

我们在之前的章节中学习了std.BitSet，它提供了一个编译时固定大小的位集合。然而，在许多场景中，我们需要的位数在编译时是未知的，或者需要动态增长。这就是std.BitBag发挥作用的地方。

std.BitBag是一个动态分配的位集合，可以根据需要增长。它就像ArrayList和BitSet的结合体，为处理可变数量的布尔标志或集合提供了极大的便利和内存效率。

2. 定义：`BitBag`

std.BitBag是一个结构体，它使用一个分配器来管理一块内存，并将其解释为位的集合。

初始化一个BitBag需要一个分配器：

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // 初始化一个空的BitBag
    var flags = std.BitBag.init(allocator);
    defer flags.deinit();

    // ... 使用flags
}

3. 操作：`set`, `unset`, `test`

BitBag提供了在任意索引处操作位的基本方法。

set(index: usize) !void: 将指定索引的位设置为1（true）。如果索引超出现有容量，BitBag会自动扩容。
unset(index: usize): 将指定索引的位设置为0（false）。如果索引越界，此操作无效。
test(index: usize) bool: 检查指定索引的位是否为1。如果索引越界，返回false。
count() usize: 返回集合中被设置为1的位的数量（汉明权重）。

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var permissions = std.BitBag.init(allocator);
    defer permissions.deinit();

    try permissions.set(10); // 设置第10位
    try permissions.set(120); // 设置第120位，BitBag会自动扩容

    std.debug.print("Permission 10 enabled: {}\n", .{permissions.test(10)}); // true
    std.debug.print("Permission 50 enabled: {}\n", .{permissions.test(50)}); // false

    permissions.unset(10);
    std.debug.print("Permission 10 enabled after unset: {}\n", .{permissions.test(10)}); // false

    std.debug.print("Total permissions enabled: {d}\n", .{permissions.count()}); // 1
}

4. 范围操作：`setRange`, `unsetRange`, `testRange`

BitBag还提供了一组强大的范围操作方法，可以高效地处理连续的位块。

setRange(range: std.Range(usize)) !void: 将一个范围内的所有位设置为1。
unsetRange(range: std.Range(usize)) !void: 将一个范围内的所有位设置为0。
testRange(range: std.Range(usize)) bool: 检查一个范围内的所有位是否都为1。

// 将索引从20到30（不含30）的所有位设置为1
try permissions.setRange(.{ .start = 20, .end = 30 });

std.debug.print("All bits in 20..25 set: {}\n", .{permissions.testRange(.{ .start = 20, .end = 25 })});

permissions.unsetRange(.{ .start = 22, .end = 28 });

5. 示例：管理一组动态权限

假设一个系统中有很多权限项，每个用户可以拥有其中的任意组合。权限ID是动态添加的。BitBag是存储每个用户权限集的理想选择。

const User = struct {
    id: u32,
    permissions: std.BitBag,
};

// ...

// 为新用户创建一个空的权限集
var user = User{ .id = 123, .permissions = std.BitBag.init(allocator) };

// 赋予用户新的权限ID 500
const PERMISSION_CAN_DELETE_FILES = 500;
try user.permissions.set(PERMISSION_CAN_DELETE_FILES);

// 检查权限
if (user.permissions.test(PERMISSION_CAN_DELETE_FILES)) {
    std.debug.print("User {d} can delete files.\n", .{user.id});
}

6. 实践练习：位压缩

编写一个函数，接收一个[]bool切片，并使用BitBag将其压缩。再编写一个函数，将BitBag解压缩回[]bool切片。比较原始切片和BitBag所占用的内存大小。

7. 常见问题

与std.BitSet有何不同？ 主要区别在于内存管理。BitSet的大小在编译时固定，通常在栈上分配。BitBag的大小是动态的，在堆上分配，并且可以按需增长。
性能如何？ 单个位的操作非常快。范围操作经过了优化，可以一次性操作整个usize块（通常是64位），而不是逐位操作，因此也非常高效。
字节序重要吗？ BitBag抽象了底层的字节和位顺序，因此你无需担心字节序问题。你只需按索引操作位即可。

8. 总结：`std.BitSet`的动态扩展

std.BitBag填补了std.BitSet留下的空白，为需要动态大小位集合的场景提供了一个灵活、高效且易于使用的解决方案。它结合了动态数组的灵活性和位集的内存效率，是处理大量布尔标志、权限集或任何其他需要按位进行密集存储和操作的数据的理想选择。掌握BitBag可以让你在处理这类问题时编写出更简洁、更高效的代码。

Day 58: std.bit_bag模块：位袋操作

1. 引言：动态位集

2. 定义：BitBag

3. 操作：set, unset, test

4. 范围操作：setRange, unsetRange, testRange