对表示大整数的结构进行算术运算

Question

我已经编写了 Murmur3 哈希的实现并将 128 位密钥定义为 hash128_t

typedef struct
{
    uint64_t p1;
    uint64_t p2;
} hash128_t;

我正在尝试使用这些键编写我自己的哈希图，但我不确定如何使用结构或这么大的数字进行算术运算。我特别需要有关模运算的帮助，但如果能帮助我将这两个内存块视为一个整数，我们将不胜感激。

我的取模公式是

Dividend - ((Dividend/Divisor) * Divisor)

Answer 1

您可以做的最简单的事情就是简单地丢弃一半的哈希并在另一半上做模（简单地使用 %）。

下一个最简单的事情是使用现有的 bignum 库。

不过，如果你想使用整个散列，你需要在这里做一个长除法。有很多方法可以实际做到这一点；这是一个（完全未经测试）的方法：

uint64_t big_modulo(hash128_t hash, uint64_t divisor) {
    uint64_t accum = hash.p1 % divisor;
    uint64_t shift_buf = hash.p2;

    for (int i = 0; i < 64; i++) {
      accum = accum << 1 | (shift_buf >> 63);
      shift_buf = shift_buf << 1;
      if (accum & (~1LU << 63)) accum = accum % divisor;
    }

    return accum % divisor;
}

请注意，如果除数大于 2^63 - 1，这将中断。修复此问题留给 reader 练习，如果您可以将除数限制为 32 位 space.

，则可以进行各种优化。

对表示大整数的结构进行算术运算

Arithmetic on a struct representing a large integer

c

math

largenumber

integer-arithmetic