Anzahl der Einträge in einem SET ermitteln

[Baeuerle]

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

[nicodex]

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

[Baeuerle]

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

[negaH]

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

[Baeuerle]

@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

[nicodex]

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;

[Baeuerle]

@nicodex: Super vielen Dank.

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

[nicodex]

Kein Ursache, der Code lag so in meinem Archiv

[himitsu]

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.

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.