Bit twiddling
Mark Scandariato
<>
Thu Mar 31 23:19:39 CEST 2005
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" <> 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