[fpc-pascal] Bitcounting

[Santiago A.]

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  -  fpc-pascal at lists.freepascal.org
> http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal


-- 
Santiago A.
svaa at ciberpiula.net