Bit twiddling
Richard A. O'Keefe
ok@REDACTED
Fri Apr 1 03:58:02 CEST 2005
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.
More information about the erlang-questions
mailing list