c++ - 有效获取 mpz_t 结构的最高有效字节

Question

我无法找到 gmpxx 是如何存储 mpz_t 结构的。因此，获取存储为 mpz_t 的数字的最高有效字节的唯一方法是使用 mpz_get_str 方法，但我预计它会非常慢。

您知道更有效(和简单)的方法吗？

我的意思是二进制数字的“最高有效字节”(在我的例子中保存为 mpz_t)。 IE。对于 12345 (10) = 11000000111001 (2) 它将是 11000000，无论 gmpxx 是否实际存储它。

Answer 1

这里要看两个函数:size_t mpz_sizeinbase(mpz_t op, int base):返回基数的长度，对于 base=2，它给出位数。void mpz_tdiv_r_2exp (mpz_t r, const mpz_t n, mp_bitcnt_t b):这等同于 r = n >> b;。结合起来，您正在寻找的操作是向右移位正好 sizeinbase-8次:

size_t bit_length = mpz_sizeinbase(number, 2);
mpz_tdiv_r_2exp(last_byte, number, bit_length-8);

作为旁注，mpz_t 结构存储在“肢体”中，它们是链接在一起的原语。这些肢体可以有前导 0，以便更轻松地编辑数字以进行小值更改 - 因此不建议直接访问它们。

A limb means the part of a multi-precision number that fits in a single machine word. (We chose this word because a limb of the human body is analogous to a digit, only larger, and containing several digits.) Normally a limb is 32 or 64 bits. The C data type for a limb is mp_limb_t. ~https://gmplib.org/manual/Nomenclature-and-Types.html#Nomenclature-and-Types