# Bit twiddling Classic List Threaded 10 messages Open this post in threaded view
|

## Bit twiddling

 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
Open this post in threaded view
|

## Bit twiddling

 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, Bits-1). twiddle(_, _, _, 0, _, -1) -> none; twiddle(_, H, L, C, _, -1) -> {H-1,L-1,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, Post-1). 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 >
Open this post in threaded view
|

## Bit twiddling

 In reply to this post by Joel Reymont-2 "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.htmlHacker's Delight   http://www.hackersdelight.org/Count number of On bits in an integer   http://www-db.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           <> ->               isize_byte(X);           <> ->               isize_bytes([X3,X2,X1,X0]);           <> ->               K = S - 1,               <<_:K/binary, Top>> = Ds,               isize_byte(Top)+K*8;           <> ->               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 :-)
Open this post in threaded view
|

## Bit twiddling

 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 >           <> -> >               isize_byte(X); >           <> -> >               isize_bytes([X3,X2,X1,X0]); >           <            Ds:S/binary>> -> >               K = S - 1, >               <<_:K/binary, Top>> = Ds, >               isize_byte(Top)+K*8; >           <            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 :-) >
Open this post in threaded view
|

## Bit twiddling

 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 >>           <> -> >>               isize_byte(X); >>           <> -> >>               isize_bytes([X3,X2,X1,X0]); >>           <>            Ds:S/binary>> -> >>               K = S - 1, >>               <<_:K/binary, Top>> = Ds, >>               isize_byte(Top)+K*8; >>           <>            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 :-) >> > >
Open this post in threaded view
|

## Configuration update

 In reply to this post by Mark Scandariato-3 Is there a way to refresh the node/application's configuration by rereading the content of the sys.config (or application-specific 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 OTP-way 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?
Open this post in threaded view
|

## Bit twiddling

 In reply to this post by Joel Reymont-2 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> <> = <>. <<165>> 3> lists:foldl(fun(N,Acc) -> N+Acc end, 0, [A,B,C,D,E,F,G,H]). 4 ------------- Cheers, Tobbe
Open this post in threaded view
|

## Bit twiddling

 In reply to this post by Mark Scandariato-3 >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): Folks, A big thanks to all who replied! I now have a lot of solutions to choose from :D.     Thanks, Joel -- http://wagerlabs.com/tech