# Bitcounting Classic List Threaded 12 messages Open this post in threaded view
|

## Bitcounting

 Hi, Does FreePascal have a routine for counting bits? So that e.g. BitCount(%1001100100001) gives 5 (number of bits that are 1)? I came up with (extracted from IntToBin()): function BitCount(N: Int64): Integer; var   Q: QWord;   i: Integer; begin   Result := 0;   Q := QWord(N);   for i := 0 to (8 * SizeOf(N) - 1) do   begin     if ((Q and 1) = 1) then Inc(Result);     Q := Q shr 1;   end; end; Surely this can be done better? Bart _______________________________________________ fpc-pascal maillist  -  [hidden email] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Open this post in threaded view
|

## Re: Bitcounting

 pseudocode length( strChange( intToStr( N), '0', '')); ________________________________________ De: [hidden email] <[hidden email]> em nome de Bart <[hidden email]> Enviado: sábado, 5 de março de 2016 15:03 Para: FPC-Pascal users discussions Assunto: [fpc-pascal] Bitcounting Hi, Does FreePascal have a routine for counting bits? So that e.g. BitCount(%1001100100001) gives 5 (number of bits that are 1)? I came up with (extracted from IntToBin()): function BitCount(N: Int64): Integer; var   Q: QWord;   i: Integer; begin   Result := 0;   Q := QWord(N);   for i := 0 to (8 * SizeOf(N) - 1) do   begin     if ((Q and 1) = 1) then Inc(Result);     Q := Q shr 1;   end; end; Surely this can be done better? Bart _______________________________________________ fpc-pascal maillist  -  [hidden email] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal_______________________________________________ fpc-pascal maillist  -  [hidden email] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Open this post in threaded view
|

## Re: Bitcounting

 In reply to this post by Bart-48 sorry ... need change intToStr in my suggestion by something like intToStrBin length( strChange( intToStrBin( N, '0', '')); but it is just for fun! ________________________________________ De: [hidden email] <[hidden email]> em nome de Bart <[hidden email]> Enviado: sábado, 5 de março de 2016 15:03 Para: FPC-Pascal users discussions Assunto: [fpc-pascal] Bitcounting Hi, Does FreePascal have a routine for counting bits? So that e.g. BitCount(%1001100100001) gives 5 (number of bits that are 1)? I came up with (extracted from IntToBin()): function BitCount(N: Int64): Integer; var   Q: QWord;   i: Integer; begin   Result := 0;   Q := QWord(N);   for i := 0 to (8 * SizeOf(N) - 1) do   begin     if ((Q and 1) = 1) then Inc(Result);     Q := Q shr 1;   end; end; Surely this can be done better? Bart _______________________________________________ fpc-pascal maillist  -  [hidden email] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal_______________________________________________ fpc-pascal maillist  -  [hidden email] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Open this post in threaded view
|

## Re: Bitcounting

 In reply to this post by Bart-48 On Sat, 5 Mar 2016 19:03:24 +0100, Bart ([hidden email]) wrote about "[fpc-pascal] Bitcounting" (in <[hidden email]>): > Does FreePascal have a routine for counting bits? [snip] > Surely this can be done better? If you don't mind a bit of C, attached is what I use. It is blazingly fast compared to examining each bit. It uses ASCIIZ strings, but can easily be converted to Pascal and AnsiStrings (or whatever). However, I'll leave that to you. -- Regards, Dave  [RLU #314465] *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-* [hidden email] (David W Noon) *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-* _______________________________________________ fpc-pascal maillist  -  [hidden email] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal bit_count.h (3K) Download Attachment
Open this post in threaded view
|

## Re: Bitcounting

 In reply to this post by Bart-48 On 05/03/2016 18:03, Bart wrote: > Hi, > > Does FreePascal have a routine for counting bits? > So that e.g. BitCount(%1001100100001) gives 5 (number of bits that are 1)? > > I came up with (extracted from IntToBin()): > Have a look at http://stackoverflow.com/questions/3815165/how-to-implement-bitcount-using-only-bitwise-operators_______________________________________________ fpc-pascal maillist  -  [hidden email] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Open this post in threaded view
|

## Re: Bitcounting

 In reply to this post by Bart-48 En Sat, 05 Mar 2016 12:03:24 -0600, Bart <[hidden email]> escribió: > Hi, > > Does FreePascal have a routine for counting bits? > So that e.g. BitCount(%1001100100001) gives 5 (number of bits that are   > 1)? > > I came up with (extracted from IntToBin()): > > function BitCount(N: Int64): Integer; > var >   Q: QWord; >   i: Integer; > begin >   Result := 0; >   Q := QWord(N); >   for i := 0 to (8 * SizeOf(N) - 1) do >   begin >     if ((Q and 1) = 1) then Inc(Result); >     Q := Q shr 1; >   end; > end; > > Surely this can be done better? > > Bart function BitCount(N: Int64): Integer; var    i: Integer; begin    Result := 0;    if N=0 then      exit;    for i := 0 to (8 * SizeOf(N) - 1) do    begin      if (N and (1 shl i)) <> 0 then Inc(result);    end; end; not tested :D Jesus Reyes A. _______________________________________________ fpc-pascal maillist  -  [hidden email] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Open this post in threaded view
|

## Re: Bitcounting

 In reply to this post by Bart-48 The PopCount functions do exactly that. On 03/05/2016 07:03 PM, Bart wrote: > Hi, > > Does FreePascal have a routine for counting bits? > So that e.g. BitCount(%1001100100001) gives 5 (number of bits that are 1)? > > I came up with (extracted from IntToBin()): > > function BitCount(N: Int64): Integer; > var >    Q: QWord; >    i: Integer; > begin >    Result := 0; >    Q := QWord(N); >    for i := 0 to (8 * SizeOf(N) - 1) do >    begin >      if ((Q and 1) = 1) then Inc(Result); >      Q := Q shr 1; >    end; > end; > > Surely this can be done better? > > Bart > _______________________________________________ > fpc-pascal maillist  -  [hidden email] > http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal> _______________________________________________ fpc-pascal maillist  -  [hidden email] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Open this post in threaded view
|

## Re: Bitcounting

 In reply to this post by Bart-48 On 05/03/16 19:03, Bart wrote: > Does FreePascal have a routine for counting bits? > So that e.g. BitCount(%1001100100001) gives 5 (number of bits that are 1)? FPC 3.x has system.popcnt Jonas _______________________________________________ fpc-pascal maillist  -  [hidden email] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Open this post in threaded view
|

## Re: Bitcounting

 In reply to this post by Bart-48 El 05/03/16 a las 19:03, Bart escribió: > Hi, > > Does FreePascal have a routine for counting bits? > So that e.g. BitCount(%1001100100001) gives 5 (number of bits that are 1)? > > I came up with (extracted from IntToBin()): > > function BitCount(N: Int64): Integer; > var >   Q: QWord; >   i: Integer; > begin >   Result := 0; >   Q := QWord(N); >   for i := 0 to (8 * SizeOf(N) - 1) do >   begin >     if ((Q and 1) = 1) then Inc(Result); >     Q := Q shr 1; >   end; > end; > > Surely this can be done better? function BitCount_for(N: Int64): Integer; var   Q: QWord;   i: Integer; begin   Result := 0;   Q := QWord(N);   for i := 0 to (8 * SizeOf(N) - 1) do   begin     inc(result,(Q and 1));     Q := Q shr 1;   end; end; function BitCount_while(N: Int64): Integer; var   Q: QWord;   i: Integer; begin   Result := 0;   Q := QWord(N);   While Q>0 do begin     inc(result,(Q and 1));     Q := Q shr 1;   end; end; The while version is slower if the first bit is 1 > > Bart > _______________________________________________ > fpc-pascal maillist  -  [hidden email] > http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal-- Santiago A. [hidden email] _______________________________________________ fpc-pascal maillist  -  [hidden email] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Open this post in threaded view
|

## Re: Bitcounting

 In reply to this post by Jonas Maebe-2 On 3/5/16, Jonas Maebe <[hidden email]> wrote: > FPC 3.x has system.popcnt Thanks. I see it's a compilerproc. How can I see how it'simplemented? Bart _______________________________________________ fpc-pascal maillist  -  [hidden email] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal