Zitat von
Stevie:
Jo, soweit bin ich auch gekommen, aber ich wollte halt eine allgemeingültige Lösung. Geht sowas überhaupt?
Ja !!!
Und zwar gibt es da eine
sehr interessante Lösung dafür (nur leider find ich den Artikel nicht mehr im Internet).
Eine Menge (=Set) ist im Speicher nur eine Anzahl von Bytes (max 32 Bytes = Menge mit 256 Elementen). Zum Zählen der gesetzten Bits in der Menge braucht es einen Zeiger auf die Mengenvariable und die Grösse der Menge (mit sizeof(TMengentyp)).
Anstatt die gesetzten Bits einzeln zu zählen, wird das Abbild der Menge in Nibbles (4 Bit) zerteilt und dann baut man sich eine
Lookuptabelle, in der die Anzahl Bits für alle 16 Möglichkeiten eines Nibbles ausgerechnet sind:
Code:
Bits Anzahl
=============
0000 = 0
0001 = 1
0010 = 1
0011 = 2
0100 = 1
0101 = 2
0110 = 2
0111 = 3
1000 = 1
1001 = 2
1010 = 2
1011 = 3
1100 = 2
1101 = 3
1110 = 3
1111 = 4
Delphi-Quellcode:
function CountBitsInNibble(x:Byte):Integer;
const
lu : packed array[0..15] of Byte = (0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4);
begin
Result := lu[x];
end;
Die Anzahl der gesetzten Bits in einem Speicherbereich ist dann auch ganz einfach:
Delphi-Quellcode:
function CountBitsInMem(x:Pointer; size:Integer):Integer;
var
i : Integer;
b : Byte;
begin
Result := 0;
for i := 0 to size-1 do
begin
b := PByte(x)^; // hole ein Byte
Inc(PByte(x)); // erhöhe der Zeiger auf den Speicher
// unteres Nibble
Inc(Result, CountBitsInNibble(b and $0F));
// oberes Nibble
Inc(Result, CountBitsInNibble(b shr 4));
end;
end;
Man könnte auch eine Tabelle für ein ganzes Byte aufbauen, man bräuchte dann aber 256 Bytes im
RAM
statt 16 Bytes für ein Nibble.
Will man die
Anzahl der nicht gesetzten Bits zählen ist dies auch ganz einfach:
Delphi-Quellcode:
function CountNullBitsInMem(x:Pointer; size:Integer):Integer;
begin
// pro Byte sind es 8 Bit
// Anzahl der Bits, die auf 0 sind ist die Gesamtanzahl aller Bits minus
// der Anzahl der gesezten Bits
Result := (size * 8)-CountBitsInMem(x, size);
end;