Bitcounting

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

Bitcounting

Bart-48
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
Reply | Threaded
Open this post in threaded view
|

Re: Bitcounting

philippe sylvain levi
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
Reply | Threaded
Open this post in threaded view
|

Re: Bitcounting

philippe sylvain levi
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
Reply | Threaded
Open this post in threaded view
|

Re: Bitcounting

David W Noon-3
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
Reply | Threaded
Open this post in threaded view
|

Re: Bitcounting

Martin Friebe
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
Reply | Threaded
Open this post in threaded view
|

Re: Bitcounting

Jesus Reyes A.
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
Reply | Threaded
Open this post in threaded view
|

Re: Bitcounting

Jeppe Johansen-3
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
Reply | Threaded
Open this post in threaded view
|

Re: Bitcounting

Jonas Maebe-2
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
Reply | Threaded
Open this post in threaded view
|

Re: Bitcounting

Santiago A.
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
Reply | Threaded
Open this post in threaded view
|

Re: Bitcounting

Bart-48
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
Reply | Threaded
Open this post in threaded view
|

Re: Bitcounting

Jonas Maebe-2
On 05/03/16 23:12, Bart wrote:
> 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?

The "compilerproc" modifier does not influence code generation other
than symbol mangling. You can just look at the implementation in the
system unit like for any other routine.

It's however not just a compilerproc, but also an intrinsic. This means
that the compiler knows about this routine, and may substitute it with
more efficient code on some platforms. To know whether it does so in
your case with your particular compiler version and compiler settings,
you have to look at the generated assembler code.


Jonas
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Bitcounting

Bart-48
On 3/5/16, Jonas Maebe <[hidden email]> wrote:


> The "compilerproc" modifier does not influence code generation other
> than symbol mangling. You can just look at the implementation in the
> system unit like for any other routine.

Lazarus code-tools didn't get me there ;-)
Found it in compilerproc.inc.

Thanks.

Bart
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal