Bit twiddling

[Thomas Lindgren]

--- Joel Reymont <joelr1@REDACTED> wrote:
> Folks,
> 
> What's the most effective way to do bit twiddling in
> Erlang? 
> 
> Should I convert the int into a list of bits? How
> would I efficiently do this?

No, a list of bits is not the way to go.

> I'm looking to figure out the highest and lowest bit
> set in an integer as
> well as count the number of bits set.

I won't claim these to be ultimately fast, but they
can serve as a starting point.

All of the following work by breaking down the integer
into a number of subfields, then using the subfield to
index into a table, and finally summing the results.
The table implementation is what differs.

Note: these won't work for negative numbers.

1.
The straightforward approach is to define a function
as a lookup table, e.g. something like:

-module(bits).
-export([count_byte/1, ...]).

%% simple 4-bit lookup table

count_bits(2#0000) -> 0;
count_bits(2#0001) -> 1;
count_bits(2#0010) -> 1;
...
count_bits(2#1111) -> 4.

%% count bits per integer

count(X) -> count(X, 0).

count(0, N) -> N;
count(X, N) -> 
   count(X bsr 4, N + count_bits(X band 15)).

%% if you have, say, a 4-byte int, then try unrolling
%% the above loop into eight count_bits calls and see
%% if that's faster

2. The lookup table could alternatively be implemented
as an ets-table, which you have to populate
beforehand. Ets is a bit messier to use, but if you
are indexing on a large subword (a short, even?), it
might scale better than using a function as a table
like above. Here is the equivalent of the above loop. 

count_bits(0, N) -> N;
count_bits(X, N) ->
   case ets:lookup(?bit_table, X band ?mask) of
      [{_X, NumBits}] -> 
         count_bits(X bsr ?shift, N+NumBits);
      [] -> %% oops
         exit({bad_value, X band ?mask});
   end.

3. Or a third kind of lookup table: use the humble
tuple as a vector. In this case, create a tuple where
position N holds the number of bits in N (or N-1):

Create table:
   Table = list_to_tuple([0, 1, 1, ...])

Note that you can create very large tuples if you
like, but do pass the Table around in the loop once
you have created it. Repeatedly evaluating Table = ...
will end in tears, performancewise.

Index into it:

   ...
   Index = X band 15,
   NumBits = element(Index+1, Table),
   ...

(Since tuple indexing is 1-based, we have to adjust
Index)

Highest and lowest bit can be coded as variations of
the above.

Best,
Thomas


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com