Parität eines Bytes

[Boxi B. (boxi)]

hab mir folgende Funktion zur Paritätsermittlung eines Bytes ausgedacht:

//Parität: 0 gerade, 1 ungerade
UI8 parity(UI8 arg)
{
  UI8 retval = 0;
  
  while (arg != 0)
  {
    retval ^= arg;
    arg >>= 1;
  }

  return (retval & 0x01);
}

Kann das funktionieren?
Gruß
Boxi

[helmi (Gast)]

Hey
Ich habs ausprobiert es funktioniert.

[Boxi B. (boxi)]

danke dir.

bei mir soweit auch, aber weißt ja wie das is. Sicherer, wenn nochmal 
jemand drüberschaut

[Morin (Gast)]

Jo scheint auch von der Theorie her in Ordnung zu sein.

[Tom (Gast)]

XOR ist hier in der Tat gut geeignet.

"Einfache" Leute würden vielleicht die Anzahl Einsen abzählen, und am 
Ende gucken, ob es gerade oder ungerade ist. Damit gucken sie aber das 
letzte Bit an. Das bedingte Increment macht auf dem letzten Bit effektiv 
ein XOR mit dem Bitwert.

Ich glaube, ich habe mich nicht besonders verständlich ausgedrückt :-(

[Peter D. (peda)]

Und wenns etwas fixer sein darf:

//Parität: 0 gerade, 1 ungerade
UI8 parity(UI8 arg)
{
  arg ^= arg >> 4;
  arg ^= arg >> 2;
  arg ^= arg >> 1;
  return (arg & 0x01);
}

Peter

[helmi (Gast)]

@peter

Bei dir musst der Prozessor immer 7 mal schieben wenn er keinen Befehl 
hat der Mehrfachverschiebung ermöglicht.

Bei der Routine von Boxi wird im einfachsten Fall (0) gar nicht 
geschoben.

Also kann man nicht sagen das deine Routine immer schneller ist.

Gruss Helmi

[Peter (Gast)]

Peters Funktion ist im Durchschnitt besser, wegen der konstanten 
Laufzeit (immer 3 XOR und 3 shifts).

[Kai G. (runtimeterror)]

Ich denke schon, dass Peters Routine in den meisten Übersetzungen im 
Mittel schneller sein dürfte.

Boxis Variante wird im Schnitt immer noch etwa 7 mal durchlaufen 
(1793/256 um genau zu sein) - der Vergleich+Sprung für Schleife ist 
nicht zu vernachlässigen.

Peters Version bietet dem Compiler recht viele Optimierungsansätze. Die 
Shift-Operation '>> 4' kann in einem Mega16 z.B. durch
SWAP oder MUL ersetzt werden. Ersteres kostet 1, zweiteres kostet 2 
Zyklen. Man kommt also für die garantierten 7 Schiebevorgänge mit 4 
Zyklen aus.

Mir ist bis jetzt nichts Schnelleres eingefallen.

Gruß

Kai

Ach ja... und die konstante Laufzeit von Peters Algorithmus gefällt mir 
besser ;)

[Tom (Gast)]

> Mir ist bis jetzt nichts Schnelleres eingefallen.

Tabelle?

(Die Gegenargumente sind mir geläufig, aber wenn es um Speed um jeden 
Preis geht...)

[Kai G. (runtimeterror)]

>Tabelle?

Ok, gewonnen :)

(Hatte ich wegen der drohenden Gegenargumente auch ausgeblendet)

[helmi (Gast)]

Wenn man auf PC Prozessoren bleibt gehts noch einfacher.

JP             Jump on Parity
JNP            Jmp on No Parity

[Hagen R. (hagen)]

SETP  Register

geht dort auch.

[Peter D. (peda)]

helmi wrote:
> Wenn man auf PC Prozessoren bleibt gehts noch einfacher.


Beim 8051 auch:
[c]
#include <reg51.h>

//Parität: 0 gerade, 1 ungerade
bit parity(char arg)
{
  ACC = arg;
  return P;
}


Peter

[Boxi B. (boxi)]

habe die beiden Versionen mal interessehalber für den HC12 kompiliert. 
Das Bild zeigt, was rausgekommen is.

Speicherbedarf:
Peters Variante: 0x17 Bytes
meine:           0x16 Bytes

zur Funktionslaufzeit, siehe die Überlegungen weiter oben.

[Falk B. (falk)]

@ Boxi Boxitec (boxi)

>Dateianhang: parity.JPG (70,9 KB, 1 Downloads)

Bildformate die 199te!

>Peters Variante: 0x17 Bytes
>meine:           0x16 Bytes

Hat der HC12 keinen SWAP Befehl? Oder ist der Compiler zu doof den zu 
nutzen?

MFG
Falk

[Boxi B. (boxi)]

Moin Falk,
>
> Bildformate die 199te!
>

Ich versteh dein ständiges Genöhle über Bildformate nicht. Kannst du mir 
bitte erklären, was ich falsch gemacht hab. Dies erschließt sich meinem 
einfach strukturiertem Hirn leider nicht aus dem Bildformate-Link und 
deinem Kommentar dazu.
Danke


Was würdest du denn gerne ge'swapped' haben?

[Falk B. (falk)]

@ Boxi Boxitec (boxi)

>Ich versteh dein ständiges Genöhle über Bildformate nicht. Kannst du mir
>bitte erklären, was ich falsch gemacht hab. Dies erschließt sich meinem
>einfach strukturiertem Hirn leider nicht aus dem Bildformate-Link und
>deinem Kommentar dazu.

Das ist wirklich schade, um nicht zu sagen bedenklich! Im 
Deutschunterricht gab es mal als Übung u.a. des Verstehen von 
Sachtexten, gabs auch in Mathematik, Textaufgaben etc. Ich versuchs mal 
pädagogisch.

Welcher Art ist dein angehängtes Bild?
In welchem Format ist es gespeichert?
Was empfiehlt der Wikiarikel für ein Format für diese Art Bilder?
Warum wird das Format empfohlen?

>Was würdest du denn gerne ge'swapped' haben?

Die 4 mal lsl kann ein AVR mittlels SWAP in EINEM Takt erledigen.

MFG
Falk

[Boxi B. (boxi)]

so?

[Falk B. (falk)]

@ Boxi Boxitec (boxi)

>Dateianhang: parity.PNG (18,7 KB, 1 Downloads)

>so?

GENAU!

MFG
Falk

[Boxi B. (boxi)]

Danke Herr Lehrer, bekomm ich jetzt ein Fleißbienchen?

;)

[Falk B. (falk)]

@ Boxi Boxitec (boxi)

>Danke Herr Lehrer, bekomm ich jetzt ein Fleißbienchen?

Wieso? Du has die Nachprüfung bestanden, mehr nicht. ;-)

MFG
Falk

[Helmi (Gast)]

Ich habe gerade mal meinen HC12 Compiler von COMIC angeschmissen.
Auch der macht kein SWAP daraus sonder shiftet 4 mal.
Auch im HC12 Instructionset Manulal von FreeScale steht kein SWAP 
Befehl.

Der kanns halt nicht.

Also ist Boxi's Routine um 1 Byte kuerzer.

Gruss Helmi

[Boxi B. (boxi)]

also mein Compiler war von COSMIC ;) S12X V4.6i/Patch1

und der kann auch kein SWAP in den Controller reinzaubern, weil er 
schlicht keins hat.

[Kai G. (runtimeterror)]

Ist ehrlich gesagt auch nicht einfach für den Compiler zu erkennen, dass 
hier auch ein SWAP geht - da es ja de facto was Anderes tut als der 
4er-Shift.

In C gibt's keine Notation für Bitrotationen, oder? - Das sollte der 
Compiler dann besser umsetzen können.

@Boxi
>Ich versteh dein ständiges Genöhle über Bildformate nicht. Kannst du mir

Na ja... es gibt halt einfach keinen Vorteil jpg zu verwenden... Das 
Bild wird größer, unscharf und kann nicht sinnvoll weiterverarbeitet 
werden. Aber passt ja jetzt :)

Gruß

Kai

[Armin (Gast)]

Alternativ und noch ein bisschen schneller geht's mit der 
Modulo-Operation:

UI8 parity(UI8 arg)
{
  arg = arg%2;
  return (arg);
}

[Peter (Gast)]

Alternativ und noch ein bisschen schneller geht's mit der
Modulo-Operation:

Armin schrieb:
> Alternativ und noch ein bisschen schneller geht's mit der
> Modulo-Operation:

6 Setzen.


Modulo hat recht wenig mit Pariät zu tun.

3 und 6 habe die gleiche Parität, auch bei dir?

[Tim S. (maxxie)]

Das gibt dir allein an ob eine Zahl gerade oder ungerade ist (Teilbar 
ohne Rest durch 2)

Nicht, ob die Anzahl der gesetzten Bits gerade oder ungerade ist.