只有 17% 的 64 位整数是两个 32 位整数的乘积

背景

在软件编程中，整数乘法通常会产生溢出（overflow），即结果被截断为固定的位数。以 8 位无符号整数为例，如果将 127 乘以 127，得到的结果是 1（因为 $127 \times 127 = 16129$，而 16129 的二进制表示超过了 8 位，只保留了低 8 位）。要完整表示 16129，通常需要 16 位的精度。

由此引出了“完整乘积”（full product）的概念。两个 32 位整数相乘的完整乘积通常用 64 位来表示。作者 Daniel Lemire 关注的核心问题是：在所有 64 位整数中，有多少比例可以表示为两个 32 位整数的乘积？

这一看似纯数学的问题，实际上与哈希函数（hash functions）的设计密切相关。哈希函数是一种将输入映射为看似随机输出的特殊函数。几年前，作者设计了一个名为 clhash 的高速字符串哈希函数，它特别适用于几百字节或更长的字符串。clhash 使用了一种在密码学应用中常见的乘法类型。作者试图论证这种方法相比基于标准乘法的技巧具有优势，而理解 32 位整数乘积在 64 位空间中的分布情况，是理解这一优势的关键。

核心内容

简单哈希函数的局限性

为了说明问题，作者首先展示了一个简单的 32 位哈希函数示例，该函数将 32 位整数的最高 16 位与最低 16 位相乘：

// simpleHighLowHash is a simple (and weak) 32-bit hash
// that multiplies the high 16 bits by the low 16 bits.
func simpleHighLowHash(x uint32) uint32 {
    high := uint16(x >> 16)
    low := uint16(x & 0xFFFF)
    return uint32(high) * uint32(low)
}

一个好的哈希函数应当是均匀的（uniform），即所有可能的 32 位哈希值出现的概率应相等。然而，上述函数无法产生所有的 32 位哈希值，因此它不是均匀的。

数学背景：Erdös 的定理

伟大的数学家 Paul Erdös 证明了，当位数 $n$ 变得非常大时，由两个 $n$ 位整数的乘积所能生成的 $2n$ 位值的比例趋于零。这意味着，如果使用极大的整数（例如 1000 万位），其乘积能覆盖的空间比例微乎其微。

但在实际工程中，我们更关心 32 位或 64 位这样的“实用”规模。对于 16 位整数的乘积（生成 32 位结果），可以通过暴力穷举轻松计算：大约只有 20% 的 32 位整数是两个 16 位整数的乘积。这意味着约 80% 的 32 位整数无法通过这种哈希方式产生。然而，暴力法的时间复杂度呈指数级增长，无法直接扩展到 32 位整数的情况。

核心问题：32 位乘 32 位的情况

作者将问题扩展到 64 位场景：如果我们将一个 64 位整数的最高 32 位与最低 32 位相乘，能产生多少种不同的 64 位结果？

func simpleHighLowHash(x uint64) uint64 {
    high := uint32(x >> 32)
    low := uint32(x & 0xFFFFFFFF)
    return uint64(high) * uint64(low)
}

能否得到精确结果？答案是肯定的。

精确计算结果

Webster 及其同事开发了相关的数学工具，使得这种精确计算可以扩展到更大的规模，并公开了其代码。计算结果显示：

• 在所有可能的 64 位（无符号）整数中，有 3,215,709,724,700,470,902 个整数可以表示为两个 32 位整数的乘积。
• 这约占所有可能 64 位整数值的 17%。

换句话说，如果你随机选择一个 64 位整数，它通常不能表示为两个 32 位整数的乘积。

如何判断一个数是否为乘积？

如果已知一个 64 位整数 $n$，如何判断它是否能分解为两个小于 $2^{32}$ 的因子？一种方法是计算其完整的质因数分解，然后构建所有严格小于 $2^{32}$ 的除数。

算法逻辑如下：

1. 初始化候选集合，仅包含 1。
2. 遍历每个质因数及其重数，将现有候选值乘以质因数的幂次，保留结果小于 $2^{32}$ 的值。
3. 为避免重复，处理唯一质因数时需考虑其重数。
4. 最终选择最大的候选值 $m$ 作为小于 $2^{32}$ 的最大除数。
5. 计算剩余部分 $n / m$，并检查其是否也小于 $2^{32}$。如果是，则存在有效的 32 位因子对；否则不存在。

Python 伪代码示例：

for p in factor_multiplicities:
    new_candidates = []
    for c in candidates:
        for i in range(factor_multiplicities[p] + 1):
            if c * (p ** i) < 2**32:
                new_candidates.append(c * (p ** i))
    for new_c in new_candidates:
        candidates.append(new_c)

m = max(candidates)
print(f"Maximum candidate: {m}")
leftover = n // m
print(f"Leftover: {leftover}")
if leftover >= 2**32:
    print("Leftover is too large, cannot find a suitable candidate.")

虽然可能存在更高效的算法，但这一过程证实了大多数 64 位整数无法被分解为两个 32 位整数。

关键要点

• 稀疏性结论：只有约 17% 的 64 位无符号整数可以表示为两个 32 位整数的乘积。
• 哈希均匀性：简单的“高低位相乘”哈希函数无法覆盖所有可能的哈希值空间，导致分布不均匀。
• 数学依据：Erdös 的定理表明，随着位数增加，乘积能覆盖的比例趋于零，但在 32/64 位这种实际规模下，17% 是一个具体且显著的数值。
• 计算可行性：通过质因数分解和候选集构建算法，可以精确判断一个 64 位整数是否由两个 32 位整数相乘得到。
• 随机性直觉：随机选取一个 64 位整数，它极大概率不是两个 32 位整数的乘积。

意义与影响

这一发现对高性能哈希函数和密码学算法的设计具有直接指导意义：

1. 验证 clhash 的优势：作者设计的 clhash 使用了非标准的乘法技巧，其目的正是为了克服传统乘法在哈希空间覆盖上的稀疏性问题。如果仅依赖简单的 32x32->64 乘法，哈希函数将无法均匀地映射到整个 64 位空间，从而降低碰撞抵抗能力和随机性表现。
2. 算法设计的启示：在需要均匀分布的哈希场景中，不能假设乘法运算能自然覆盖所有输出空间。设计者必须显式地处理这种稀疏性，或者使用更复杂的混合运算（如异或、旋转等）来填充未被乘积覆盖的“空洞”。
3. 性能与正确性的权衡：虽然暴力穷