c - 代表大整数的结构上的算术

我写了一个murdur3散列的实现，并将128位密钥定义为hash128_t

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

我正试图用这些键来编写自己的hashmap，但我不确定如何使用结构或这么大的数字来进行算术运算我特别需要关于模运算的帮助，但是关于如何将这两个内存块视为一个整数的帮助将非常有用。
我的模公式是

Dividend - ((Dividend/Divisor) * Divisor)

最佳答案

你能做的最简单的事情就是丢弃一半散列，在另一半上做模运算（简单地使用%）。
下一步最简单的做法是使用现有的BigNem库。
如果你想使用整个散列，你需要在这里做一个长除法有很多方法可以做到这一点；以下是一种（完全未经测试的）方法：

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，这将中断把这个修改留给读者去做，如果可以将除数限制在32位空间中，可以进行各种各样的优化。