broadword-rs: 广字算法

此软件包包含广字算法，它将 u64 视为八个 u8 或 i8 的并行向量，以及计数和选择算法。

使用方法

它在 crates.io 上，因此您可以将

[dependencies]
broadword = "0.2.2"

添加到您的 Cargo.toml 中，并

extern crate broadword;

添加到您的 crate 根目录。

lib.rs:

广字操作将 u64 视为八个 u8 或 i8 的并行向量。此模块还提供了一个计数函数 count_ones 和一个选择函数 select1。

这里的算法来自 Sebastiano Vigna, “Broadword Implementation of Rank/Select Queries,” 但对此工作进行了几处修改

• Vigna 使用了 17 位的（68 位）常量“0x0F0F0F0F0F0F0F0F0。”我相信正确的常量是这 64 位：0x0F0F_0F0F_0F0F_0F0F。

• 算术运算假定在溢出时回绕。如果不是这样，算法 1 （count_ones）在乘以 L₈ 时会溢出其最后一行。

• 算法 2 的第 2 行应为

  s = (s & 0x3333_3333_3333_3333) + ((s >> 2) & 0x3333_3333_3333_3333);
  

  在论文中，位移后的 s 出现在 x 中。