mysql - 两个整数mysql的汉明距离

Question

mysql 模式和查询在这里

http://sqlfiddle.com/#!9/444873/1

查询似乎有效并只返回行汉明距离小于 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 将向上 1(与 LHS 相同，没问题)或向下 1(仍然可以， RHS 允许小于 LHS，但这就是它不相等的原因)
• 如果我们在两者前加一个 1，它们的 XOR 不会改变，所以 LHS 保持不变。在 RHS 中，两个 popcnts 都增加 1，它们相互抵消，因此 RHS 也保持不变。

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