Счетчик битов или вес Хемминга строки битов в эликсире?

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.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не справляется с ними.

Использовать

Вместо этого я бы предложил использовать мощный Эликсир.<<>>оператор битовой строки (который также выглядит лучше 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

---