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

pseudocode
length( strChange( intToStr( N), '0', ''));

________________________________________
De: em nome de Bart
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

sorry ... need change intToStr in my suggestion by something like intToStrBin
length( strChange( intToStrBin( N, '0', ''));

but it is just for fun!

________________________________________
De: em nome de Bart
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

On Sat, 5 Mar 2016 19:03:24 +0100, Bart () wrote
about "[fpc-pascal] Bitcounting" (in
):

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.

Have a look at
http://stackoverflow.com/questions/3815165/how-to-implement-bitcount-using-only-bitwise-operators

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.

The PopCount functions do exactly that.

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

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

Jonas Maebe wrote

FPC 3.x has system.popcnt

Thanks.
I see it's a compilerproc.
How can I see how it'simplemented?

Bart

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

Jonas Maebe 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