c++ - 模位集算法

Question

假设我有 2 个位集

bitset<1024> test, current;

我应该如何取模 current与 test并在另一个 bitset<1024> 中输出？注意 test可以是任何形式，而不仅仅是 2 的幂？

寻找完整代码或完整伪代码的答案。除了bitset，我不会接受涉及转换为另一种类型的答案。因为虽然在这里使用 bitsets 可能会工作得更慢，但在程序后面的 bitsets 会非常快。

Answer 1

如果您不想自己实现取模算法，可以尝试以下方法:

1. 代替std::bitset，使用boost::dynamic_bitset .
2. 使用boost::to_block_range将位集的字节复制到缓冲区。
3. 使用众多 bigint 库之一来表示一个 256 字节的整数。
4. 使 256 字节的 bigint 使用在步骤 #2 中复制的字节。
5. 对 bigint 进行模运算。
6. 将结果转换回 dynamic_bitset。
7. 利润

希望有一个 bigint 库可以让您访问它的缓冲区，这样您就可以将字节从 dynamic_bitset 直接复制到 bigint 中。

希望与模运算本身相比，复制 256 个字节的开销可以忽略不计。

哦，bigint 表示应该与 dynamic_bitset 具有相同的字节顺序。