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

# 仅17%的64位整数是两个32位整数的乘积 来源：https://lemire.me/blog/2026/05/22/only-17-of-all-64-bit-integers-are-products-of-two-32-bit-integers/ 在软件编程中，两个整数的乘积通常会被截断到固定的位数，产生溢出。考虑8位整数：如果你将127乘以127，作为无符号8位整数，你得到的结果是1，发生了溢出。实际的完整乘积是16129，要表示16129，通常需要16位的精度。 于是我们有了“完整乘积”的概念。两个32位整数的完整乘积通常用64位来表示。困扰我的问题是：在所有64位整数中，有多少比例可以写成两个32位整数的乘积？ 你可能会问为什么关心这个？ 我们经常设计哈希函数：它们是一种特殊函数，接收输入并生成看似随机的输出。几年前，我设计了一个非常快速的哈希函数，叫做`clhash`（https://github.com/simdhash/clhash）。它是一个针对几百字节或更长字符串的超快哈希函数。如果你不知道`clhash`，不妨看看（https://github.com/simdhash/clhash），它本身很有意思。 这个`clhash`哈希函数使用了一种在密码学应用中常见的乘法类型。我试图论证我们的方法相比基于标准乘法的技术有优势。让我举例说明。一个简单的32位整数哈希函数可以取最低有效位与最高有效位相乘。 `` // simpleHighLowHash 是一个简单（且弱）的32位哈希函数， // 它将高16位和低16位相乘。 func simpleHighLowHash(x uint32) uint32 { high := uint16(x >> 16) low := uint16(x & 0xFFFF) return uint32(high) * uint32(low) } `` 你可能希望哈希函数是均匀的：所有可能的32位哈希值应具有相同的概率。但在这个例子中，只有当哈希函数能够生成所有32位哈希值时才有可能，而实际情况并非如此。 伟大的数学家埃尔德什曾证明：所有`2n`位值中能被两个`n`位值乘积生成的比例，随着`n`变大而趋近于零。这意味着，如果使用10000000位整数相乘，能够产生的100000000000000位整数会非常少。但对于实际场景，比如32位整数或64位整数呢？ 我们可以用暴力方法轻松处理16位整数相乘得到32位乘积的情况。此时，略微超过五分之一的32位数是两个16位整数的乘积。大约80%的32位整数永远不会被这个哈希产生。然而，运行时间指数增长，暴力方法无法扩展到32位。 那么对于32位的情况该怎么办？也就是说，当你将两个32位整数相乘得到64位乘积时，下面的函数能产生多大比例的64位值？ `` func simpleHighLowHash(x uint64) uint64 { high := uint32(x >> 16) low := uint32(x & 0xFFFFFFFF) return uint64(high) * uint64(low) } `` 我们能得到精确的结果吗？ 能！！ Webster（https://blue.butler.edu/~jewebste/）和他的同事们建立了数学基础（https://arxiv.org/pdf/1908.04251），使得我们可以精确计算更大规模的情况。他很慷慨地公开了代码（https://github.com/jewebste/multiplication-table-problem）。 共有 3,215,709,724,700,470,902 个64位（无符号）整数可以写成两个32位整数的乘积。这大约占所有可能值的17%。 [](https://lemire.me/blog/wp-content/uploads/2026/05/products_percentage.png) 那么如何根据乘积计算出两个整数呢？一种方法是：首先计算其完整的质因数分解，然后利用这些因子构建所有严格小于`2^32`的除数。从仅包含`1`的候选集合开始，迭代地将每个质因子乘进现有候选中（只保留乘积仍小于`2^32`的项）。通过处理唯一质因子及其多重性，我们可以避免向集合中添加重复项。最后，选择最大的候选`m`作为小于`2^32`的最大除数，计算对应的剩余部分`n / m`，并报告是否存在有效的两个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"最大候选值: {m}") leftover = n // m print(f"剩余部分: {leftover}") if leftover >= 2**32: print("剩余部分过大，无法找到合适的候选值。") `` 你或许能想出更高效的算法。我觉得有意思的是：如果你随机选一个值，它通常是不满足条件的！也就是说，大多数64位整数无法写成两个32位整数的乘积。