

Folks,
What's the most effective way to do bit twiddling in Erlang?
Should I convert the int into a list of bits? How would I efficiently do this?
I'm looking to figure out the highest and lowest bit set in an integer as
well as count the number of bits set.
Thanks, Joel

http://wagerlabs.com/tech


If you have a binary you could do something hideous like:
%%%%%%%%%%%%%%%%
module(foo).
export([twiddle/1]).
twiddle(Bin) when is_binary(Bin) >
Bits = 8 * size(Bin),
twiddle(Bin, 1, Bits+1, 0, 0, Bits1).
twiddle(_, _, _, 0, _, 1) > none;
twiddle(_, H, L, C, _, 1) > {H1,L1,C};
twiddle(Bin, H, L, C, Pre, Post) >
<<_:Pre, X:1, _:Post>> = Bin,
{H1,L1} = hilo(X, H, L, Post+1),
twiddle(Bin, H1, L1, C+X, Pre+1, Post1).
hilo(0, H, L, _) > {H, L};
hilo(1, H, L, C) > {max(H,C), min(L,C)}.
min(A, B) when A < B > A;
min(_, B) > B.
max(A, B) when A > B > A;
max(_, B) > B.
%%%%%%%%%%%%%%%%
1> foo:twiddle(<<9876:16>>).
{13,2,6}
2>
Mark.
Joel Reymont wrote:
> Folks,
>
> What's the most effective way to do bit twiddling in Erlang?
>
> Should I convert the int into a list of bits? How would I efficiently do this?
>
> I'm looking to figure out the highest and lowest bit set in an integer as
> well as count the number of bits set.
>
> Thanks, Joel
>


"Joel Reymont" <joelr1> 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.htmlHacker's Delight
http://www.hackersdelight.org/Count number of On bits in an integer
http://wwwdb.stanford.edu/~manku/bitcount/bitcount.htmlHighest 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/bigunsignedinteger, 0,
Ds:S/binary>> >
K = S  1,
<<_:K/binary, Top>> = Ds,
isize_byte(Top)+K*8;
<<?VERSION_MAGIC, ?LARGE_BIG_EXT, S:32/bigunsignedinteger, 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 :)


So, based on http://wwwdb.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 (N1)), 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, BMagic]) >
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,BMagic]) >
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, []) > Z1;
tzb0(N, Z, [S, BMagic]) >
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, bitbybit" will provide, in O(N), all three results
on arbitrary Nbit sequences.
Mark.
Luke Gorrie wrote:
> "Joel Reymont" <joelr1> 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://wwwdb.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/bigunsignedinteger, 0,
> Ds:S/binary>> >
> K = S  1,
> <<_:K/binary, Top>> = Ds,
> isize_byte(Top)+K*8;
> <<?VERSION_MAGIC, ?LARGE_BIG_EXT, S:32/bigunsignedinteger, 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 :)
>


Mark Scandariato wrote:
> So, based on http://wwwdb.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 (N1)), 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, BMagic]) >
> 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,BMagic]) >
> 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, []) > Z1;
> tzb0(N, Z, [S, BMagic]) >
> 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, BMagic]) >
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, bitbybit" will provide, in O(N),
> all three results on arbitrary Nbit sequences.
>
> Mark.
>
> Luke Gorrie wrote:
>
>> "Joel Reymont" <joelr1> 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://wwwdb.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/bigunsignedinteger, 0,
>> Ds:S/binary>> >
>> K = S  1,
>> <<_:K/binary, Top>> = Ds,
>> isize_byte(Top)+K*8;
>> <<?VERSION_MAGIC, ?LARGE_BIG_EXT, S:32/bigunsignedinteger, 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 :)
>>
>
>


Is there a way to refresh the node/application's configuration by
rereading the content of the sys.config (or applicationspecific config)
file without restarting the node?
Since the content of the config file becomes a part of the application's
environment at node startup, I want to ensure that I can dynamically
change the configuration (by making changes in the config file), and
force the application to refresh its environment with the changes.
What's the OTPway to address this problem?
Thanks.
Serge
P.S.
I found an undocumented application_controller:change_application_data/2
function. Am I looking in the right direction?


Joel Reymont wrote:
>Folks,
>
>What's the most effective way to do bit twiddling in Erlang?
>
>Should I convert the int into a list of bits? How would I efficiently do this?
>
>I'm looking to figure out the highest and lowest bit set in an integer as
>well as count the number of bits set.
>
> Thanks, Joel
>
>
>
I'm not sure how efficient this is, but its an alternative
to the solutions Thomas sent:

Eshell V5.4.5 (abort with ^G)
1> I=2#10100101.
165
2> <<A:1,B:1,C:1,D:1,E:1,F:1,G:1,H:1>> = <<I:8>>.
<<165>>
3> lists:foldl(fun(N,Acc) > N+Acc end, 0, [A,B,C,D,E,F,G,H]).
4

Cheers, Tobbe


Hi,
On Thu, 20050331 at 15:39, Joel Reymont wrote:
> Folks,
>
> What's the most effective way to do bit twiddling in Erlang?
>
> Should I convert the int into a list of bits? How would I efficiently do this?
Efficiency depends on the size of your numbers.
> I'm looking to figure out the highest and lowest bit set in an integer as
> well as count the number of bits set.
For the lowest bit, if your dealing with small numbers (register size) a
nice way is to use:
last_bit(0) > undefined;
last_bit(N) > do_last_bit(N xor (N  1) ).
do_last_bit(2#1) > 0;
do_last_bit(2#11) > 1;
do_last_bit(2#111) > 2;
...
do_last_bit(2#11111111111111111111111111111111) > 31.
or if you have a good solution for first_bit
last_bit2(0) > undefined;
last_bit2(N) > first_bit(N xor (N  1) ).
For numbers bigger than register, you have to reduce their size by
removing trailing 0:
big_last_bit(N) >
Last = N band 16#ffffffff,
case Last of
0 > 32 + big_last_bit (N bsr 32);
_ > last_bit(Last)
end.

Laurent Picouleau
laurent.picouleau


I think my prior submission attempt didn't get posted during list
unavailability, so here it is again:

Is there a way to refresh the node/application's configuration by
rereading the content of the sys.config (or applicationspecific config
provided on command line, such as: "erl config "file...") file without
restarting the node?
Since the content of the config file becomes a part of the application's
environment at node startup, I want to ensure that I can change the
configuration (by making changes in the config file using text editor),
and force the application to refresh its environment with the new
changes from file. Merely trying to restart an application on a running
node doesn't reread the config file's content.
What's the OTPway to address this problem?
Regards,
Serge
P.S.
I found an undocumented application_controller:change_application_data/2
function. Am I looking in the right direction?

