std::hash乘法溢出场景下求解满足x*mul=hash2的多组x的方法

首先明确你要解决的问题本质是64位无符号整数模2^64乘法的逆运算，对应等式可写为：
(x * mul) & 0xFFFFFFFFFFFFFFFF == hash2
其中x就是你要找的shift_mix(hash1)取值。

因为你用到的常量mul = 0xc6a4a7935bd1e995UL是奇数，和2^64互质，因此64位取值范围内x有且仅有唯一解，不存在多组64位解；如果需要超出64位的解，只需要在唯一64位解的基础上叠加k * 2^64即可，k为任意整数，所有这类取值乘以mul后的低64位都等于hash2。

你观察到的hash2 / mul = 0是普通整数除法的结果，对模2^64逆运算没有参考价值，不要用普通除法尝试求解。

最优实现方式：预计算乘法逆元 #

模2^64下奇数的乘法逆元可以快速预计算，之后每次求解x只需要一次64位乘法，性能最高。

1. 首先计算mul的模2^64逆元，代码示例：

#include <cstdint>
uint64_t calc_mod_inv_2p64(uint64_t a) {
    // 仅对奇数a有效
    uint64_t inv = 1;
    for (int i = 0; i < 6; ++i) {
        inv *= 2 - a * inv;
    }
    return inv;
}
const uint64_t mul = 0xc6a4a7935bd1e995UL;
const uint64_t inv_mul = calc_mod_inv_2p64(mul);

2. 任意hash2对应的x直接按如下方式计算，无符号64位乘法会自动取低64位，符合要求：

uint64_t x = hash2 * inv_mul;

借助__int128的实现方式 #

__int128可以用来验证解的正确性，也可以用来计算逆元，但求解效率和预计算逆元的方式没有差异，验证代码示例：

bool verify_solution(uint64_t x, uint64_t hash2) {
    __int128_t full_res = (__int128_t)x * mul;
    return (uint64_t)full_res == hash2;
}

如果需要生成多组超出64位的解，也可以用__int128存储x，拼接64位解和任意高位值即可。

内容的提问来源于stack exchange，提问作者Владимир Говорухин