Bit twiddling

[Mark Scandariato]

So, based on http://www-db.stanford.edu/~manku/bitcount/bitcount.html, something like 
these might do (for 32bit or smaller ints):

%% number of bits set
% bits0 works on arbitrary integers.
bits0(N) when N >= 0-> bits0(N, 0).
bits0(0, C) -> C;
bits0(N, C) ->
     bits0((N band (N-1)), C+1).

bits1(0) -> 0;
bits1(N) when N > 0, N < 16#100000000 ->
     bits1(N, [1,  16#55555555,
               2,  16#33333333,
               4,  16#0F0F0F0F,
               8,  16#00FF00FF,
               16, 16#0000FFFF]).

bits1(N, []) -> N;
bits1(N, [S, B|Magic]) ->
     bits1(((N bsr S) band B) + (N band B), Magic).


%% log2, aka, position of the high bit
log2(N) when N > 0, N < 16#100000000 ->
     log2(N, 0, [16, 16#FFFF0000, 8, 16#FF00, 4, 16#F0, 2, 16#C, 1, 16#2]).

log2(_, C, []) -> C;
log2(N, C, [S,B|Magic]) ->
     if (N band B) == 0 -> log2(N, C, Magic);
         true -> log2((N bsr S), (C bor S), Magic)
     end.

%% trailing zero bits, aka position of the lowest set bit.
tzb0(N) when N > 0, N < 16#100000000 ->
     tzb0(N, 32, [16, 16#0000FFFF,
                  8,  16#00FF00FF,
                  4,  16#0F0F0F0F,
                  2,  16#33333333,
                  1,  16#55555555]).

tzb0(_, Z, []) -> Z-1;
tzb0(N, Z, [S, B|Magic]) ->
     if (N band B) == 0 -> tzb(N, Z, Magic);
        true -> tzb(0(N bsl S), (Z - S), Magic)
     end.


tzb1(N) when N > 0,  N < 16#100000000 ->
     Mod = {32,0,1,26,2,23,27,0,3,16,24,30,
            28,11,0,13,4,7,17,0,25,22,31,15,
            29,10,12,6,0,21,14,9,5,20,8,19,18},
     P = (-N band N) rem 37,
     element(P+1, Mod).


Although my naive "walk the binary, bit-by-bit" will provide, in O(N), all three results 
on arbitrary N-bit sequences.

Mark.

Luke Gorrie wrote:
> "Joel Reymont" <joelr1@REDACTED> writes:
> 
> 
>>I'm looking to figure out the highest and lowest bit set in an integer as
>>well as count the number of bits set.
> 
> 
> If it needs to be fast then be sure to see what mathematician
> assembler hackers have to say!
> 
> hackmem
>   http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
> 
> Hacker's Delight
>   http://www.hackersdelight.org/
> 
> Count number of On bits in an integer
>   http://www-db.stanford.edu/~manku/bitcount/bitcount.html
> 
> Highest bit set is floor(log2(N)) if you figure out the floating
> point, though Erlang doesn't have a log2 BIF. Tony Rogvall has a very
> interesting "how many bits is this integer" function that makes the
> runtime system do the real work in jungerl/lib/ssh/src/ssh_bits.erl:
> 
>   isize(N) when N > 0 ->
>       case term_to_binary(N) of
>           <<?VERSION_MAGIC, ?SMALL_INTEGER_EXT, X>> ->
>               isize_byte(X);
>           <<?VERSION_MAGIC, ?INTEGER_EXT, X3,X2,X1,X0>> ->
>               isize_bytes([X3,X2,X1,X0]);
>           <<?VERSION_MAGIC, ?SMALL_BIG_EXT, S:8/big-unsigned-integer, 0,
>            Ds:S/binary>> ->
>               K = S - 1,
>               <<_:K/binary, Top>> = Ds,
>               isize_byte(Top)+K*8;
>           <<?VERSION_MAGIC, ?LARGE_BIG_EXT, S:32/big-unsigned-integer, 0,
>            Ds:S/binary>> ->
>               K = S - 1,
>               <<_:K/binary, Top>> = Ds,
>               isize_byte(Top)+K*8
>       end;
>   isize(0) -> 0.
> 
> i.e. encode the number in the binary Erlang external term format and
> then pull that apart to see the length header :-)
>