jarrodm
Ingest a bitstring from least significant bit
Hi all,
I’ve finally achieved ‘Basic’ status on Elixir Forums, so I have a appropriately basic question 
I’m ingesting a mask where each power of 2 aligns to an consecutive index. So, a value of 1, flags the first index, 2 → 2nd, 4-> 3rd, etc. I’m using the default big endianness of the VM, and I’m finding the following:
iex(87)> << 0::1, 1::7 >> = << 1 >>
<<1>>
… whereas I desire something like:
iex(87)> << 1::1, 0::7 >> = some_transform(<< 1 >>)
<<1>>
I’ve mucked around with big and little modifiers on either side of the match operator, but I assume the order of ingest when the bitstring is split is predetermined to be most-significant/lowest-bit to least-significant/highest-bit, low-byte to high-byte, and the input byte will always be in the same bit-order—which all makes sense. I see that there’s :binary encode and decode functions, but once again they only affect byte order, as it should.
I’ve resolved to doing:
(for << bit::1 <- << 1 >> >>, into: [], do: bit)
|> Enum.reverse()
… to reverse the bits so that I can ingest them the way I expect. Though I suspect I’ve missed some obvious easier way, or some erlang function that might be endian-agnostic, and maybe even optimize this away to a trivial assembly operation—am I hoping too much?
Any pointers would be much appreciated 
Thanks!
Most Liked
ityonemo
defmodule M do
def lastbit(bitstring) do
size = bit_size(bitstring) - 1
<<_head :: size(size), bit :: 1 >> = bitstring
bit
end
def reverse_string_map(bitstring, f, so_far \\ [])
def reverse_string_map(<<>>, _, so_far), do: Enum.reverse(so_far)
def reverse_string_map(bitstring, f, so_far) do
headsize = bit_size(bitstring) - 1
<<head :: size(headsize), bit :: 1 >> = bitstring
reverse_string_map(<<head::size(headsize)>>, f, [f.(bit) | so_far])
end
end
iex> M.reverse_string_map(<<0b01001::5>>, &IO.inspect/1)
1
0
0
1
0
[1, 0, 0, 1, 0]
unfortunately, I have no idea where the full list of string bit length decorators is documented. Note that generally you can’t have a variable size at the head of a string, but in this case we can calculate it and go and do it explicitly. But you can’t just drop a variable directly in to the length specifier (laaaame), so you have to explicitly invoke the size() decorator.
Sebb
Endianess is not about the bit-order, but about byte order.
iex(1)> <<number::big-integer-size(16)>> = <<0, 0::6, 1::1, 0::1>>
<<0, 2>>
iex(2)> number
2
iex(3)> <<number::little-integer-size(16)>> = <<0, 0::6, 1::1, 0::1>>
<<0, 2>>
iex(4)> number
512
In a bitstring the least significant bit is the rightmost and there is nothing you can do about it.
jarrodm
So I ran some tests. I had to modify your code to match my function signature. Specifically you were running a function for each value, whereas mine was simply reversing the bit string. Here are the results:
Random 16-bit bitstrings
Name ips average deviation median 99th %
comprehension and reverse 23.44 K 42.67 μs ±183.57% 40 μs 99 μs
function style 2 16.58 K 60.32 μs ±55.19% 56 μs 138 μs
comprehension w/ reduce + bitwise operations 11.84 K 84.47 μs ±126.03% 76 μs 180 μs
function style 6.54 K 153.01 μs ±45.05% 135 μs 427 μs
Comparison:
comprehension and reverse 23.44 K
function style 2 16.58 K - 1.41x slower +17.65 μs
comprehension w/ reduce + bitwise operations 11.84 K - 1.98x slower +41.80 μs
function style 6.54 K - 3.59x slower +110.34 μs
Random 8-bit bitstrings
Name ips average deviation median 99th %
comprehension and reverse 47.36 K 21.12 μs ±82.42% 19 μs 48 μs
function style 2 32.93 K 30.37 μs ±38.18% 28 μs 64 μs
comprehension w/ reduce + bitwise operations 23.59 K 42.40 μs ±48.22% 38 μs 91 μs
function style 14.11 K 70.85 μs ±41.83% 64 μs 154 μs
Comparison:
comprehension and reverse 47.36 K
function style 2 32.93 K - 1.44x slower +9.25 μs
comprehension w/ reduce + bitwise operations 23.59 K - 2.01x slower +21.28 μs
function style 14.11 K - 3.36x slower +49.73 μs
It appears the simplest approach is the fastest, with your second implementation coming in second. I’m surprised that my second implementation is worse than my first, but it probably that erlang doesn’t permit reusing registers to do ‘in-place’ updates to values, but throws everything on the stack - or perhaps there’s some contention between registers. So it looks like the KISS principle wins on the erlang VM.
You can find the .exs for the benchmark here:
Edit: And please let me know if I’ve made any mistakes with the benchmark
Popular in Questions
Other popular topics
Latest on Elixir Forum
Sponsor Spotlight
Supporting innovation across the BEAM ecosystem.
Categories:
Sub Categories:
Forums
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Develop your skills with books, videos, and courses.
Enabling companies to succeed by building software people love.
The deployment platform built for Elixir: PaaS ease, VPS control.
Courses that'll move you from confusion to "Aha, now I get it!"