Bit twiddling

Laurent Picouleau <>
Fri Apr 1 15:59:13 CEST 2005


Hi,

On Thu, 2005-03-31 at 15:39, Joel Reymont 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?

Efficiency depends on the size of your numbers.

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

For the lowest bit, if your dealing with small numbers (register size) a
nice way is to use:

last_bit(0) -> undefined;
last_bit(N) -> do_last_bit(N xor (N - 1) ).

do_last_bit(2#1) -> 0;
do_last_bit(2#11) -> 1;
do_last_bit(2#111) -> 2;
...
do_last_bit(2#11111111111111111111111111111111) -> 31.

or if you have a good solution for first_bit

last_bit2(0) -> undefined;
last_bit2(N) -> first_bit(N xor (N - 1) ).

For numbers bigger than register, you have to reduce their size by
removing trailing 0:

big_last_bit(N) ->
	Last = N band 16#ffffffff,
	case Last of
	0 -> 32 + big_last_bit (N bsr 32);
	_ -> last_bit(Last)
	end.

-- 
Laurent Picouleau
   




More information about the erlang-questions mailing list