Bit twiddling

Thomas Lindgren thomasl_erlang@REDACTED
Thu Mar 31 17:56:00 CEST 2005

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

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

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

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

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


Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 

More information about the erlang-questions mailing list