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))
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
While Patrick's answer is correct for positive integers, it will fail for negative numbers since :binary.encode_unsigned/1
does not handle them.
<<>>
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>>
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With