在SQLite3中计算64位有符号整数汉明距离并筛选Top5哈希

你的查询存在三个核心问题：

1. 异或计算错误：ABS(signed_hash - reference_signed_hash)完全不等于两个数的异或结果。汉明距离的本质是两个数异或后二进制中1的个数，减法和异或是完全不同的运算，尤其是在有符号整数的补码场景下，结果会完全偏离预期。
2. 无限递归风险：64位有符号整数右移时，负数会进行符号扩展（比如-1右移后还是-1），导致xor_result > 0的终止条件永远无法满足，触发无限递归。
3. 重复记录未去重：递归CTE会为每个xor_result的每一位生成一条记录，最终查询会返回同一signed_hash的多条重复行，排序和LIMIT结果完全错误。

以下是适配64位有符号整数的正确查询，分两种场景：

场景1：数据库支持内置位计数函数（如MySQL、PostgreSQL、SQL Server） #

大部分现代数据库都提供了直接计算二进制中1的个数的函数，这是最高效的方式：

-- 以MySQL/PostgreSQL为例，SQL Server语法类似
SELECT 
  signed_hash,
  BIT_COUNT(signed_hash ^ reference_signed_hash) AS hamming_distance
FROM hashdb
ORDER BY hamming_distance ASC, signed_hash ASC
LIMIT 5;

• 解释：signed_hash ^ reference_signed_hash直接计算两个数的异或，BIT_COUNT（PostgreSQL为bit_count）统计异或结果中1的位数，也就是汉明距离。
• 注意：Oracle数据库中异或用BITXOR(signed_hash, reference_signed_hash)，计数用BIT_COUNT（Oracle 12c+支持）。

场景2：数据库无内置位计数函数（兼容通用SQL） #

如果你的数据库没有位计数函数，用递归CTE的正确写法如下：

WITH RECURSIVE HammingDistance AS (
  SELECT 
    signed_hash,
    -- 转为无符号整数避免符号扩展问题
    CAST(signed_hash ^ reference_signed_hash AS UNSIGNED BIGINT) AS xor_result,
    0 AS hamming_distance
  FROM hashdb
  UNION ALL
  SELECT 
    signed_hash,
    xor_result >> 1,
    hamming_distance + (xor_result & 1)
  FROM HammingDistance
  WHERE xor_result > 0
)
-- 取每个signed_hash的最终汉明距离
SELECT signed_hash, MAX(hamming_distance) AS hamming_distance
FROM HammingDistance
GROUP BY signed_hash
ORDER BY hamming_distance ASC, signed_hash ASC
LIMIT 5;

• 关键修正：
  1. 用signed_hash ^ reference_signed_hash替代减法，正确计算异或。
  2. 将异或结果转为无符号64位整数，避免右移时的符号扩展，确保递归能终止。
  3. 通过GROUP BY和MAX(hamming_distance)获取每个哈希值的最终汉明距离，去除重复记录。

• 确保reference_signed_hash替换为你实际要对比的参考值。
• 如果数据库不支持UNSIGNED BIGINT，可以用位掩码0xFFFFFFFFFFFFFFFF实现无符号逻辑（如signed_hash ^ reference_signed_hash & 0xFFFFFFFFFFFFFFFF）。

内容的提问来源于stack exchange，提问作者enigmatic