Datenbits effektiv zählen

[shmia]

Hi,

mit der folgende Funktion kann man die Anzahl der gesetzten Datenbits in einem Speicherbereich zählen.
Das Besondere daran ist, dass mit Hilfe einer Lookup Tabelle immer gleich 4 Bits auf einmal gezählt werden.
Deshalb ist die Funktion sehr schnell. Eine Lookup Tabelle mit 256 Einträgen wäre noch schneller, aber das lohnt den Aufwand nicht.

Delphi-Quellcode:

function CountBitsSet(P: Pointer; Count: Cardinal): Cardinal;
const
  lu : packed array[0..15] of Byte = (0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4);
var
  b: Byte;
begin
  Result := 0;
  while Count > 0 do
  begin
    b := PByte(P)^;
    // lower Nibble
    Inc(Result, lu[b and $0F]);
    // upper Nibble
    Inc(Result, lu[b shr 4]);

    Dec(Count);
    Inc(PByte(P));
  end;
end;

diese Funktion findet sich auch in der Unit JclLogic aus der JCL, denn ich habe sie bei JCL eingereicht.
Man kann sich nun auch noch für die üblichen Datentypen ein überladene Funktion bauen:

Delphi-Quellcode:

function CountBitsSet(X: Integer): Integer;
begin
  Result := CountBitsSet(@X, sizeof(X));
end;

Um die Anzahl der gelöschten Bits zu zählen:

Delphi-Quellcode:

function CountBitsCleared(P: Pointer; Count: Cardinal): Cardinal;
begin
  result := Count*8-CountBitsSet(P: Pointer; Count: Cardinal);
end;