两个二进制字符串之间的距离跨度

Question

有什么方法可以有效地（按位运算）找到两个 8 位二进制字符串的距离（不是汉明距离！）？

每个字节保证只有一位设置。

喜欢：

a=0 0 0 0 0 0 0 1
b=0 0 0 1 0 0 0 0

  0 0 0 1 0 0 0 1 -> distance = 3
          ^^^^^ 
------
a=0 0 0 0 0 1 0 0
b=0 1 0 0 0 0 0 0

  0 1 0 0 0 1 0 0 -> distance = 3
      ^^^^^
------
a=0 1 0 0 0 0 0 0
b=0 0 0 0 0 0 1 0

  0 1 0 0 0 0 1 0 -> distance = 4
      ^^^^^^^

我可以使用对数之类的东西，但效率不高

Answer 1

"Efficient" 在这里可能意味着不同的东西：例如，对于已知输入范围，渐近与性能；时间 vs space;等等

我假设您关心您描述的小范围输入的原始速度。

基线方法。取较小的位，左移它直到它等于较大的位，计算移位。虽然这是 O(n)，但这种分析在这里并不重要，因为 n 是有界的。

您可以将该基线与以下任一方法进行比较，这两种方法具有更好的时间复杂度，但对于您的输入来说可能更快也可能不会更快。

备选方案 1. 将所有距离放入查找矩阵中。 O(1) 时间复杂度，但 O(n^2) space 复杂度。

备选方案 2。查找 table 对数，return 差值 log₂ (a) - log₂(b)，其中 a >= b。 O(1) 时间复杂度，O(n) space 复杂度。（请注意，我假设 dist(a, a) = 0，这与您上面描述的相差一个。）

我不知道在实践中哪一个会更快，但要点不是假设 O(n) 意味着算法对于您的输入来说绝对速度较慢。

Answer 2

你可以用OR运算（逻辑求和），然后求一个最大的零个数，一个一个去。希望我答对了你的问题。

两个二进制字符串之间的距离跨度

Distance span between two binary strings

bit-manipulation