有效地获取 GMP 的 N 个最低位 mpz_t

Question

mpz_class GMP 类型 mpz_t 的 C++ 包装器。有 mpz_class 个数字，用它的 N 个最低位来创建另一个 mpz_class 个数字的最有效方法是什么？

当然可以做下面的屏蔽操作

size_t N = 273; // how many lo bits to take
mpz_class x = ... ; // fill with something...
mpz_class mask = (mpz_class(1) << N) - 1; // mask having N 1-bits
mpz_class result = x & mask; // final result, N lowest bits taken

但是这种掩码需要大量不必要的位与操作并减慢代码速度。也许有一些捷径，比如 result = x.take_lo(N);?

也有可能mpz_class没有这个快捷方式，但至少CAPI有这个功能吧？因为任何 mpz_class 都可以通过 mpz_t c_num = x.get_mpz_t(); 轻松转换为 C 类型 mpz_t 而无需开销。所以我可以在 C API 中使用 .take_lo(N) 快捷方式。

Answer 1

尽管 mpz_class 没有 C++ 运算符重载或函数，但您确实可以使用：C API 提供的 mpz_tdiv_r_2exp。例如，

mpz_tdiv_r_2exp(result.get_mpz_t(), x.get_mpz_t(), N);

注意：cdiv 和 fdiv 变体也可用。

使用 mp_bitcnt_t 作为 (N) 的类型，或者 static_cast<mp_bitcnt_t>(N) 作为参数，会更稳健——因为 mp_bitcnt_t 似乎被无条件地定义为 unsigned long，可能不匹配size_t。

有效地获取 GMP 的 N 个最低位 mpz_t

Efficiently take N lowest bits of GMP mpz_t

c

c++

performance

bit-manipulation

gmp