Bit twiddling

[Richard A. O'Keefe]

	Create table:
	   Table = list_to_tuple([0, 1, 1, ...])
	
Why not just write Table = {0, 1, 1, ...}?
This isn't commented, but it may be of use.

low_bit/1 could be extended to negative integers in a fairly
uncontroversial way, but hasn't been.

Bit indices are >= 0.


-module(bits).
-export([pop_count/1, high_bit/1, low_bit/1]).

pop_count(N) when integer(N), N >= 0 -> pop_count_16(N, 0).

pop_count_16(N, B) when N > 65535 ->
    pop_count_16(N bsr 16, pop_count_4(N, B));
pop_count_16(N, B) ->
    pop_count_4(N, B).

pop_count_4(N, B) ->
    pop_count_t(N bsr 12) +
    pop_count_t((N bsr 8) band 15) +
    pop_count_t((N bsr 4) band 15) +
    pop_count_t(N band 15) + B.

pop_count_t( 0) -> 0;
pop_count_t( 1) -> 1;
pop_count_t( 2) -> 1;
pop_count_t( 3) -> 2;
pop_count_t( 4) -> 1;
pop_count_t( 5) -> 2;
pop_count_t( 6) -> 2;
pop_count_t( 7) -> 3;
pop_count_t( 8) -> 1;
pop_count_t( 9) -> 2;
pop_count_t(10) -> 2;
pop_count_t(11) -> 3;
pop_count_t(12) -> 2;
pop_count_t(13) -> 3;
pop_count_t(14) -> 3;
pop_count_t(15) -> 4.


high_bit(N) when integer(N), N > 0 -> high_bit_16(N, 0);
high_bit(0) -> -1.

high_bit_16(N, B) when N > 65535 -> high_bit_16(N bsr 16, B + 16);
high_bit_16(N, B)                -> high_bit_4(N, B).

high_bit_4(N, B) when N > 15 -> high_bit_4(N bsr 4, B + 4);
high_bit_4(N, B) when N >  7 -> B + 3;
high_bit_4(N, B) when N >  3 -> B + 2;
high_bit_4(N, B) when N >  1 -> B + 1;
high_bit_4(1, B)             -> B.


low_bit(N) when integer(N), N > 0 -> low_bit_16(N, 0);
low_bit(0) -> -1.

low_bit_16(N, B) when (N band 65535) == 0 -> low_bit_16(N bsr 16, B + 16);
low_bit_16(N, B)                          -> low_bit_4(N, B).

low_bit_4(N, B) when (N band 15) == 0 -> low_bit_4(N bsr 4, B + 4);
low_bit_4(N, B) when (N band  7) == 0 -> B + 3;
low_bit_4(N, B) when (N band  3) == 0 -> B + 2;
low_bit_4(N, B) when (N band  1) == 0 -> B + 1;
low_bit_4(1, B)                       -> B.

% The end.