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

Question

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)) 

Dynamometer

Answer 1

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

Ogbomosho

Thanks for sharing, 500:1 :( – Dynamometer

Please can you shed any light on why your implementation is so much faster, it would really help. – Dynamometer

The slow part of your implementation is converting the integer to a char list. Binary pattern matching on the other hand is highly optimized. However, for a small number of digits the performance difference is negligible. – Ogbomosho

Protip: if you put the code in a file bench/hamming_bench.exs, you won't need to call Benchfella.start manually. – Jorgejorgensen

To anyone reading this who is looking to understand the reasons behind the speedup, see groups.google.com/forum/… – Jorgejorgensen

Answer 2

While Patrick's answer is correct for positive integers, it will fail for negative numbers since :binary.encode_unsigned/1 does not handle them.

Use <<>>

Instead, I would suggest using the Elixir's powerful <<>> bitstring operator (which also looks nicer IMO):

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

You can also specify the integer size as 16-bit, 32-bit, or anything else:

<<n::integer-32>>

---

Count bits in a single pass

As an alternative approach, you can also count bits directly in one go instead of first fetching all the bits and then summing them:

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

---

Malonylurea