Bit twiddling

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

Bit twiddling

Joel Reymont-2
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




Reply | Threaded
Open this post in threaded view
|

Bit twiddling

Mark Scandariato-3
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
>


Reply | Threaded
Open this post in threaded view
|

Bit twiddling

Luke Gorrie-3
In reply to this post by Joel Reymont-2
"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://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 :-)




Reply | Threaded
Open this post in threaded view
|

Bit twiddling

Mark Scandariato-3
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" <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://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 :-)
>


Reply | Threaded
Open this post in threaded view
|

Bit twiddling

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):
>
> %% 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> 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 :-)
>>
>
>


Reply | Threaded
Open this post in threaded view
|

Configuration update

Serge Aleynikov-4
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?


Reply | Threaded
Open this post in threaded view
|

Bit twiddling

tobbe
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> <<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



Reply | Threaded
Open this post in threaded view
|

Bit twiddling

Joel Reymont-2
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




Reply | Threaded
Open this post in threaded view
|

Bit twiddling

Laurent Picouleau-2
In reply to this post by Joel Reymont-2
Hi,

On Thu, 2005-03-31 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



Reply | Threaded
Open this post in threaded view
|

Configuration update

Serge Aleynikov-4
In reply to this post by Serge Aleynikov-4
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 application-specific 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 OTP-way 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?