Einzelnen Beitrag anzeigen

shmia

Registriert seit: 2. Mär 2004
5.508 Beiträge
 
Delphi 5 Professional
 
#7

Re: Anzahl der Elemente in einem Mengentyp

  Alt 17. Jun 2004, 10:20
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;
Andreas
  Mit Zitat antworten Zitat