Bit-Count or Hamming-weight of a BitString in Elixir?

4
votes

Please how can we efficiently calculate the hamming-weight of a bit-string in elixir?

Example: 0b0101101001 has a Hamming-weight of 5 (i.e. 5 bits set)

My Attempt:

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

1 Answers

6
votes

Here is a better performing solution, which (for me) also shows the intention more clearly:

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

Benchmark using benchfella with 100.000 binary digits:

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

Benchmark results:

$ 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