c++ - 带unsigned int的字节数组的求余算法

Question

给定一个固定大小的 C++ 字节数组(模板函数)和一个无符号整数，我如何计算余数(通常是整数的 % 运算符)。

这是我目前使用 GMP 的方式:

template <typename HashType>
uint64_t remainder(const HashType& value, const uint64_t divisor)
{
    mpz_t integ;
    mpz_init(integ);
    mpz_import(integ, value.size(), 1, 1, 1, 0, value.data());
    uint64_t remainder = mpz_fdiv_ui(integ, divisor);
    mpz_clear(integ);
    return remainder;
}

移除 GMP 依赖并通过不需要设置和拆卸代码(只需直接使用字节数组)来提高性能会很好。

顺便说一句，是否有任何算法可以更快地找到余数，但仅适用于特定的除数子集(例如素数)？ (仅供引用，这用于哈希桶，所以如果我可以选择除数的值)

Answer 1

如果 divisor 可以超过 56 位长，而你没有可用的 128 位整数类型，那么你不能用高级语言轻易地做这个长除法.因此，您可能应该使用汇编语言(为了速度)或 GMP(为了便于编码)。

这是否回答了您的问题？或者您对 divisor 的大小有限制吗？