Erlang bit indexing

Question

I am currently trying to learn erlang and what I am trying to do is to perform an operation on specific indices of an array stored in a bit array or int. If there is a 0 in a position, the index into the array at that position is not used.

So envision the following:

Example the array is: [1, 3, 5, 42, 23]
My bit array is: 21 = 10101 in binary
so I'm using indicies 1,3,5
so I'm calling a function on [1, 5, 23]

my function is of the form

my_function(Array, BitArray) ->
    SubArray = get_subarray_from_bitarray(Array, BitArray),
    process_subarray(SubArray).

And I need help with the get_subarray_from_bitarray(). I know erlang has special syntax around bit strings (something like <<>>) so is there an efficient way of indexing into the bit array to get the indicies?

Answer 1

Most the time, Erlang works with lists and recursion, so I believe it's idiomatic to go through each bit individually rather than try to index each bit in an iterative manner.

The documentation on how to work with bitstrings is here. In order to create a bitstring from the number 21, we can write <<21>>. Since the default type for a member of a binary is integer, and the default size for an integer is 8, it will yield a bitstring that looks like 00010101. If you want to specifically get the last N bytes of a value is <<Value:N>>. In order to get the last 5 bits of 21, we can say <<21:5>> which will yield 10101.

I wrote the following module to do what you want:

-module(bitmask).
-export([get_subarray_from_bitarray/2]).

get_subarray_from_bitarray(Bitstring, List) ->
  get_subarray_from_bitarray_loop(Bitstring, List, []).

get_subarray_from_bitarray_loop(_Bits, [], Gathered) ->
  io:format("End of list~n", []),
  lists:reverse(Gathered);
get_subarray_from_bitarray_loop(<<>>, _Others, Gathered) ->
  io:format("End of bitstring~n", []),
  lists:reverse(Gathered);
get_subarray_from_bitarray_loop(<<Bit:1, Rest/bitstring>>, [Item | Others], Gathered) ->
  io:format("Bit: ~w ~n", [Bit]),
  case Bit of
    1 -> get_subarray_from_bitarray_loop(Rest, Others, [Item | Gathered]);
    0 -> get_subarray_from_bitarray_loop(Rest, Others, Gathered)
  end.

The first 2 clauses return the final list when you run out of bits or items in the list. The important bit syntax is in the head of the last clause, <<Bit:1, Rest/bitstring>>. This sets the value of Bit to the value of the first bit in the bitstring, and Rest to the rest of the bitstring. Depending on the value of Bit, we decide whether or not we add the current item to the list.

Example invocations below:

> bitmask:get_subarray_from_bitarray(<<21:5>>, [1, 3, 5, 42, 23]).   
Bit: 1 
Bit: 0 
Bit: 1 
Bit: 0 
Bit: 1 
End of list
[1,5,23]
> bitmask:get_subarray_from_bitarray(<<31>>, [1, 3, 5, 42, 23]).  
Bit: 0 
Bit: 0 
Bit: 0 
Bit: 1 
Bit: 1 
End of list
[42,23]
> bitmask:get_subarray_from_bitarray(<<5:3>>, [1, 3, 5, 42, 23]). 
Bit: 1 
Bit: 0 
Bit: 1 
End of bitstring
[1,5]

Answer 2

A possible implementation of the get_subarray_from_bitarray/2 function could be:

get_subarray_from_bitarray(Array, BitArray) ->
    gsb(Array, BitArray, []).

gsb(_, 0, R) -> lists:reverse(R);
gsb([A1|A2], B, R) ->
  NextR = if B band 1 /= 0 ->
     [A1|R];
  true ->
     R
  end,
  gsb(A2, B div 2, NextR).

I'm pretty sure it would be very nice with a list comprehension too. Left as an exercise for the reader :)