两个整数的汉明距离 mysql

Question

mysql 架构和查询在这里

查询似乎有效，returns 对我来说只有行汉明距离小于 7 位。

似乎以下属性适用：

bit_count(a ^ b ) >= abs(bit_count(a) - bit_count(b))

一些例子

                bit_count
a     1111       4
b     0000       0
a^b   1111       4

a     1010       2
b     0110       2
a^b   1100       2

a     1001       2    
b     1001       2
a^b   0000       0

上面的不等式是真的吗？

如果是，有人可以提供证明吗？

我这么问是因为如果上面的不等式成立那么我使用的索引对减少查询时间很有意义

Answer 1

这里有一个证明，它可能做得更简单，但还不错。

通过归纳位串的长度，基本情况是空串，显然不等式成立。

归纳步骤是在 A 和 B 之前添加（或附加，没有任何区别）。

如果我们在两者前面加上 0，则 popcnts 不会改变，因此不等式仍然成立。
如果我们在其中一个前面加上 0 而在另一个前面加上 1，则它们的 XOR 将再设置一位，因此 LHS 上升 1。在 RHS 中，其中一个 popcnts 上升（不不管哪个，绝对差是可交换的），因此 RHS 将 up 增加 1（与 LHS 相同，没问题）或 down 乘以 1（仍然可以，允许 RHS 小于 LHS，但这就是不相等的原因）
如果我们在两者前面加一个 1，它们的 XOR 不会改变，所以 LHS 保持不变。在 RHS 中，两个 popcnts 都增加 1，它们相互抵消，因此 RHS 也保持不变。

因此这个不等式适用于任何长度的位串。

两个整数的汉明距离 mysql

Hamming distance of two integers mysql

mysql

algorithm

math

computer-science

proof