Delphi-PRAXiS - Anzahl der Einträge in einem SET ermitteln

Delphi-PRAXiS (https://www.delphipraxis.net/forum.php)

- Programmieren allgemein (https://www.delphipraxis.net/40-programmieren-allgemein/)

- - Anzahl der Einträge in einem SET ermitteln (https://www.delphipraxis.net/119940-anzahl-der-eintraege-einem-set-ermitteln.html)

Anzahl der Einträge in einem SET ermitteln

Hallo

ich habe folgenden Code:

Delphi-Quellcode:

			type

 TType = (tyA, tyB, tyC, tyD);

var t: TType;

t=[tyA,tyD];

// Benötige so etwas

SizeOf(t); // = 2

Kann die Anzahl der Einträge nicht mit SizeOf() ermittelt werden? Warum nicht und gibt es eine bessere Methode als über jedes einzelne Element?

Ich möchte nur die Anzahl der Einträge ermitteln

Thx
Baeuerle

Re: Anzahl der Einträge in einem SET ermitteln

Im Endeffekt willst du die Bits zählen. Dafür gibt es Optimierungen...

Delphi-Quellcode:

			//

// A generalization of the best bit counting method (sideways addition)

// to integers of bit widths upto 128 (parameterized by type T) is this:

//

// v := v - ((v shr 1) and T(not T(0) div 3));

// v := (v and T(not T(0) div 15 * 3)) + ((v shr 2) and T(not T(0) div 15 * 3));

// v := (v + (v shr 4)) and T(not T(0) div 255 * 15);

// c := T(v * T(not T(0) div 255)) shr ((SizeOf(T) - 1) * ByteBits);

//

// 32-bit

Val32 := PLongWord(Data)^;

Val32 := Val32 - ((Val32 shr 1) and $55555555);

Val32 := (Val32 and $33333333) + ((Val32 shr 2) and $33333333);

Val32 := (Val32 + (Val32 shr 4)) and $0F0F0F0F;

Val32 := (Val32 * $01010101) shr 24;

// 16-bit

Val16 := PWord(Data)^;

Val16 := Val16 - ((Val16 shr 1) and $5555);

Val16 := (Val16 and $3333) + ((Val16 shr 2) and $3333);

Val16 := (Val16 + (Val16 shr 4)) and $0F0F;

Val16 := Word(Val16 * $0101) shr 8;

// 8-bit

Val08 := Data^;

Val08 := Val08 - ((Val08 shr 1) and $55);

Val08 := (Val08 and $33) + ((Val08 shr 2) and $33);

Val08 := (Val08 + (Val08 shr 4)) and $0F;

Quelle:

http://graphics.stanford.edu/~seande...ntBitsSetNaive

Re: Anzahl der Einträge in einem SET ermitteln

Danke für den Tip jedoch werde ich nicht ganz daraus schlau, wie müsste das für t (siehe oben) aussehen???

Delphi-Quellcode:

			function CNT(Data: TType): Byte;

var val: Byte;

begin

val:=Data^;

Val := Val - ((Val08 shr 1) and $55);

Val := (Val and $33) + ((Val shr 2) and $33);

Val := (Val + (Val shr 4)) and $0F;

Result:=val;

end;

Das funktioniert nicht :-(( Bitte um hilfe

thx

Re: Anzahl der Einträge in einem SET ermitteln

ohne Tricks und TypCasts gehts so:

Delphi-Quellcode:

			type

  TType = (tyA, tyB, tyC, tyD);

  TTypes = set of TType;

function CountOf(const Value: TTypes): Integer;

var

  I: TType;

begin

  Result := 0;

  for I := Low(TType) to High(TType) do

   if I in Value then 

     Inc(Result);

end;

Gruß Hagen

Re: Anzahl der Einträge in einem SET ermitteln

@Hagen: thx, die Lösung kannte ich schon. Ich möchte aber nicht schleifen.

Suche eine Lösung wie oben angedeutet, leider bekomme ich Sie nicht umgesetzt :-(

Re: Anzahl der Einträge in einem SET ermitteln

Delphi-Quellcode:

			{$RANGECHECKS OFF}

{$OVERFLOWCHECKS OFF}

function SidewaysAddition32(AValue: LongWord): LongWord; inline;

begin

  Result := AValue - ((AValue shr 1) and $55555555);

  Result := (Result and $33333333) + ((Result shr 2) and $33333333);

  Result := (Result + (Result shr 4)) and $0F0F0F0F;

  Result := (Result * $01010101) shr 24;

end;

function SidewaysAddition16(AValue: Word): Word; inline;

begin

  Result := AValue - ((AValue shr 1) and $5555);

  Result := (Result and $3333) + ((Result shr 2) and $3333);

  Result := (Result + (Result shr 4)) and $0F0F;

  Result := Word(Result * $0101) shr 8;

end;

function SidewaysAddition8(AValue: Byte): Byte; inline;

begin

  Result := AValue - ((AValue shr 1) and $55);

  Result := (Result and $33) + ((Result shr 2) and $33);

  Result := (Result + (Result shr 4)) and $0F;

end;

////////////////////////////////////////////////////////////////////////////////

procedure Foo();

type

  TBits8 = set of (bBit0, bBit1, bBit2, bBit3, bBit4, bBit5, bBit6, bBit7);

  TBits16 = set of (

    wBit0, wBit1, wBit2,  wBit3,  wBit4,  wBit5,  wBit6,  wBit7,

    wBit8, wBit9, wBit10, wBit11, wBit12, wBit13, wBit14, wBit15

    );

  TBits32 = set of(

    dBit0,  dBit1,  dBit2,  dBit3,  dBit4,  dBit5,  dBit6,  dBit7,

    dBit8,  dBit9,  dBit10, dBit11, dBit12, dBit13, dBit14, dBit15,

    dBit16, dBit17, dBit18, dBit19, dBit20, dBit21, dBit22, dBit23,

    dBit24, dBit25, dBit26, dBit27, dBit28, dBit29, dBit30, dBit31

    );

const

  Bar8: TBits8 = [bBit0, bBit3];

  Bar16: TBits16 = [wBit0];

  Bar32: TBits32 = [dBit16, dBit18, dBit31];

begin

  ShowMessage(

    IntToStr(SidewaysAddition8(Byte(Bar8))) + #13#10 +

    IntToStr(SidewaysAddition16(Word(Bar16))) + #13#10 +

    IntToStr(SidewaysAddition32(LongWord(Bar32)))

  );

end;

Re: Anzahl der Einträge in einem SET ermitteln

@nicodex: Super vielen Dank.

Mir hatte eigentliche "nur" der Typecast Byte(t) gefehlt :-)

Re: Anzahl der Einträge in einem SET ermitteln

Kein Ursache, der Code lag so in meinem Archiv ;)

Re: Anzahl der Einträge in einem SET ermitteln

Joar, also ich hatte/hab da auch grad ein kleines Problem.

Im Grunde hab ich "nur" 2 Register frei. (solange ich nicht extra noch ein paar Register-Werte kurzfristig auslagere, was ich aber eigentlich vermeiden wollte)
In EDX liegt der zu prüfende/zählende Wert und bei EAX sollen die Bits von EDX zuaddiert werden,
wobei EDX ruhig vernichtet werden kann.

Dieses geht ja leider nicht:

Delphi-Quellcode:

			ADD     EAX, BYTE PTR [@@Table + DL]

ADD     EAX, BYTE PTR [@@Table + DH]

SHR     EDX, 16

ADD     EAX, BYTE PTR [@@Table + DL]

ADD     EAX, BYTE PTR [@@Table + DH]

@@Table:

DB      0,1,1,2,1,2,2,3, 1,2,2,3,2,3,3,4, 1,2,2,3,2,3,3,4, 2,3,3,4,3,4,4,5

DB      1,2,2,3,2,3,3,4, 2,3,3,4,3,4,4,5, 2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6

DB      1,2,2,3,2,3,3,4, 2,3,3,4,3,4,4,5, 2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6

DB      2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6, 3,4,4,5,4,5,5,6, 4,5,5,6,5,6,6,7

DB      1,2,2,3,2,3,3,4, 2,3,3,4,3,4,4,5, 2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6

DB      2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6, 3,4,4,5,4,5,5,6, 4,5,5,6,5,6,6,7

DB      2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6, 3,4,4,5,4,5,5,6, 4,5,5,6,5,6,6,7

DB      3,4,4,5,4,5,5,6, 4,5,5,6,5,6,6,7, 4,5,5,6,5,6,6,7, 5,6,6,7,6,7,7,8

Ein ADDZX, also sowas wie MOVZX, welches ein Byte ausließt und zu einem ganzen Register addiert, gibt es leider auch nicht, ebenso wie der Compiler nicht so gern die Byte-Registern arbeitet.
Ich müßte diesen Code also irgendwie so zerlegen, daß er die Bytes erstmal separiert und dann einzeln rechnetwerden,
aber da kann ich auch fast meinen aktuellen Code lassen, welcher einfach die Bits einzeln über eine SHIFT-Operation prüft. :angel2:

Delphi-Quellcode:

			TEST    EDX, EDX                        //     While EDX <> 0 do Begin

JZ      @@Exit                          //

@@Loop:                                 //

JNS     @@NoInc                         //       If Odd(EDX) Then

INC     EAX                             //         Inc(Result);

@@NoInc:                                //

SHL     EDX, 1                          //       EDX := EDX shr 1;

JNZ     @@Loop                          //     End;

@@Exit:

Soooo oft wird dieser Code wohl nicht ausgeführt, als daß es sich lohnt ihn so extrem zu "optimieren", daß am Ende keiner mehr durchsieht, was da eigentlich gemacht wird.

PS: zu Code-Library -> Object-Pascal / Delphi-Language ->

Datenbits effektiv zählen
Die ~200 zusätzlichen Bytes fallen in einer "normalen" Anwendung wohl nicht wirklich auf,
aber dafür würden etwa 50% der Speicher-/Rechenoperationen eingespart.

Delphi-Quellcode:

			function CountBitsSet(P: Pointer; Count: Cardinal): Cardinal;

const

  lu : packed array[0..$FF] of Byte = (

    0,1,1,2,1,2,2,3, 1,2,2,3,2,3,3,4, 1,2,2,3,2,3,3,4, 2,3,3,4,3,4,4,5,

    1,2,2,3,2,3,3,4, 2,3,3,4,3,4,4,5, 2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6,

    1,2,2,3,2,3,3,4, 2,3,3,4,3,4,4,5, 2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6,

    2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6, 3,4,4,5,4,5,5,6, 4,5,5,6,5,6,6,7,

    1,2,2,3,2,3,3,4, 2,3,3,4,3,4,4,5, 2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6,

    2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6, 3,4,4,5,4,5,5,6, 4,5,5,6,5,6,6,7,

    2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6, 3,4,4,5,4,5,5,6, 4,5,5,6,5,6,6,7,

    3,4,4,5,4,5,5,6, 4,5,5,6,5,6,6,7, 4,5,5,6,5,6,6,7, 5,6,6,7,6,7,7,8);

begin

  Result := 0;

  while Count > 0 do

  begin

    Inc(Result, lu[PByte(P)^]);

    Inc(PByte(P));

    Dec(Count);

  end;

end;

Delphi-Quellcode:

			function CountBitsSet(P: Pointer; Count: Cardinal): Cardinal;

const

  lu : packed array[0..$FF] of Byte = (

    0,1,1,2,1,2,2,3, 1,2,2,3,2,3,3,4, 1,2,2,3,2,3,3,4, 2,3,3,4,3,4,4,5,

    1,2,2,3,2,3,3,4, 2,3,3,4,3,4,4,5, 2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6,

    1,2,2,3,2,3,3,4, 2,3,3,4,3,4,4,5, 2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6,

    2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6, 3,4,4,5,4,5,5,6, 4,5,5,6,5,6,6,7,

    1,2,2,3,2,3,3,4, 2,3,3,4,3,4,4,5, 2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6,

    2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6, 3,4,4,5,4,5,5,6, 4,5,5,6,5,6,6,7,

    2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6, 3,4,4,5,4,5,5,6, 4,5,5,6,5,6,6,7,

    3,4,4,5,4,5,5,6, 4,5,5,6,5,6,6,7, 4,5,5,6,5,6,6,7, 5,6,6,7,6,7,7,8);

begin

  Result := 0;

  while Count > 0 do

  begin

    Dec(Count);

    Inc(Result, lu[(PByte(P) + Count)^]);

  end;

end;

Beide Funktionen sind etwa gleich "langsam", wobei Letztere aber im Test die Nase um eine Haareslänge voraus war.