Bit twiddling

[Mark Scandariato]

Mark Scandariato wrote:
> 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.

Oops - that should have been:
tzb0(N, Z, [S, B|Magic]) ->
     if (N band B) == 0 -> tzb0(N, Z, Magic);
        true -> tzb0((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 :-)
>>
> 
>