Elixir中BitString的位计数或汉明权重

Question

请问我们如何efficiently计算长生不老药中位串的汉明重量？

示例：0b0101101001的汉明权重为 5(即设置 5 位(

我的尝试：

iex> Enum.count(Integer.to_char_list(n,2),&(&1===49)) 

Answer 1

这是一个性能更好的解决方案，它(对我来说(也更清楚地显示了意图：

for(<<bit::1 <- :binary.encode_unsigned(n)>>, do: bit) |> Enum.sum

使用具有 100.000 个二进制数字的 benchfella 进行基准测试：

Benchfella.start
defmodule HammingBench do
  use Benchfella
  @n Stream.repeatedly(fn -> Enum.random [0, 1] end)
    |> Enum.take(100_000)
    |> Enum.join
    |> String.to_integer(2)
  bench "CharlesO" do
    Enum.count(Integer.to_char_list(@n,2),&(&1===49)) 
  end
  bench "Patrick Oscity" do
    for(<<bit::1 <- :binary.encode_unsigned(@n)>>, do: bit) |> Enum.sum
  end
end

基准测试结果：

$ mix bench
Compiled lib/hamming_bench.ex
Generated hamming_bench app
Settings:
  duration:      1.0 s
## HammingBench
[20:12:03] 1/2: Patrick Oscity
[20:12:06] 2/2: CharlesO
Finished in 8.4 seconds
## HammingBench
Patrick Oscity         500   4325.79 µs/op
CharlesO                 1   5754094.00 µs/op

Answer 2

虽然帕特里克的答案对于正整数是正确的，但对于负数，它将失败，因为:binary.encode_unsigned/1不处理它们。

使用<<>>

相反，我建议使用Elixir强大的<<>>位串运算符(IMO看起来也更好(：

Enum.sum(for << bit::1 <- <<n>> >>, do: bit))

您还可以将整数大小指定为 16 位、32 位或其他任何内容：

<<n::integer-32>>

<小时 />单

次计数位数

作为另一种方法，您也可以一次性直接计算位，而不是先获取所有位，然后对它们求和：

defmodule HammingWeight do
  def weight(int) when is_integer(int) do
    w(<<int>>, 0)
  end
  defp w(<<>>>, count),                do: count
  defp w(<<0::1, rest::bits>>, count), do: w(rest, count)
  defp w(<<1::1, rest::bits>>, count), do: w(rest, count + 1)
end

<小时 />