如何高效提取GMP库mpz_t/mpz_class类型数值的N个最低有效位

最高效实现方案 #

GMP C API 提供了专门的内置函数 mpz_fdiv_r_2exp 实现这个需求，完全不需要自行构造掩码做按位与运算，性能远高于你当前的实现方案。

该函数的定义为：

void mpz_fdiv_r_2exp(mpz_t r, const mpz_t n, mp_bitcnt_t b);

作用是计算 n 模 2^b 的非负余数，恰好就是提取 n 的最低 b 位的结果，和你当前掩码方案的输出完全等价。

你可以很轻松的把它封装成你需要的 take_lo 工具函数，适配 C++ 的 mpz_class 类型：

#include <gmpxx.h>

mpz_class take_lo(const mpz_class& x, size_t N) {
    mpz_class res;
    mpz_fdiv_r_2exp(res.get_mpz_t(), x.get_mpz_t(), N);
    return res;
}

// 调用示例
size_t N = 273;
mpz_class x = /* 你的输入数值 */;
mpz_class result = take_lo(x, N);

性能优势说明 #

你原来的掩码方案需要先生成一个 N 位全1的大数作为掩码，再对输入值全量执行按位与运算，当 N 很大时会产生大量不必要的计算。
而 mpz_fdiv_r_2exp 内部实现直接截断高于 N 位的部分，只需要对不超过 N 位的部分做极少量运算，不需要生成掩码也不需要处理高位数据，N 越大性能优势越明显。

目前 gmpxx 没有为 mpz_class 提供对应的内置成员方法，上述封装几乎没有额外开销，性能和直接调用C API完全一致。

内容的提问来源于stack exchange，提问作者Arty