ruby - 计算 ruby 汉明距离的最有效方法？

Question

在 ruby​​ 中，计算两个无符号整数之间的位差(例如汉明距离)的最有效方法是什么？

例如，我有整数 a = 2323409845 和 b = 178264714​​4。

它们的二进制表示是:

a = 10001010011111000110101110110101
b = 01101010010000010000100101101000

a 和 b 之间的位差是 17..

我可以对它们进行逻辑异或，但这会给我一个不同的整数!= 17，然后我将不得不遍历结果的二进制表示并计算 1 的数量。

计算位差的最有效方法是什么？

现在，计算多个整数序列的位差的答案是否改变了？例如。给定 2 个无符号整数序列:

x = {2323409845,641760420,509499086....}
y = {uint,uint,uint...}

计算两个序列之间位差的最有效方法是什么？

你会遍历序列，还是有更快的方法来一次计算整个序列的差异？

Answer 1

您可以使用 Ruby 中优化的字符串函数来进行位计数，而不是纯算术。通过一些快速基准测试，结果证明速度快了大约 6 倍。

def h2(a, b)
  (a^b).to_s(2).count("1")
end

h1是正常的计算方式，h2是将异或转换成字符串，统计“1”的个数

基准:

ruby-1.9.2-p180:001:0>> def h1(a, b)
ruby-1.9.2-p180:002:1*> ret = 0
ruby-1.9.2-p180:003:1*> xor = a ^ b
ruby-1.9.2-p180:004:1*> until xor == 0
ruby-1.9.2-p180:005:2*> ret += 1
ruby-1.9.2-p180:006:2*> xor &= xor - 1
ruby-1.9.2-p180:007:2*> end
ruby-1.9.2-p180:008:1*> ret
ruby-1.9.2-p180:009:1*> end
# => nil
ruby-1.9.2-p180:010:0>> def h2(a, b)
ruby-1.9.2-p180:011:1*> (a^b).to_s(2).count("1")
ruby-1.9.2-p180:012:1*> end
# => nil
ruby-1.9.2-p180:013:0>> h1(2323409845, 1782647144)
# => 17
ruby-1.9.2-p180:014:0>> h2(2323409845, 1782647144)
# => 17
ruby-1.9.2-p180:015:0>> quickbench(10**5) { h1(2323409845, 1782647144) }
Rehearsal ------------------------------------
   2.060000   0.000000   2.060000 (  1.944690)
--------------------------- total: 2.060000sec

       user     system      total        real
   1.990000   0.000000   1.990000 (  1.958056)
# => nil
ruby-1.9.2-p180:016:0>> quickbench(10**5) { h2(2323409845, 1782647144) }
Rehearsal ------------------------------------
   0.340000   0.000000   0.340000 (  0.333673)
--------------------------- total: 0.340000sec

       user     system      total        real
   0.320000   0.000000   0.320000 (  0.326854)
# => nil
ruby-1.9.2-p180:017:0>>