Bit twiddling
Mark Scandariato
<>
Thu Mar 31 23:26:13 CEST 2005
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" <> 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 :-)
>>
>
>
More information about the erlang-questions
mailing list