Wie schnell die Quersumme bilden?

[Euklid]

Hallo Leute,

kennt jemand von Euch eine Methode, mit der man möglichst wenig CPU-Lastig die Binärquersumme einer Zahl - als sprich die Anzahl der "Eins"en der Zahl im binären System - bestimmen kann?
Mir fällt da nur die Methode ein, mithilfe der hier

http://www.lazarusforum.de/viewtopic.php?f=10&t=2752" onclick="window.open(this.href);return false;

beschriebenen Funktion getbit die Bits einzeln zu zählen. Das würde zwar gehen, kommt mir aber recht umständlich vor. Kennt jemand was einfacheres bzw. schnelleres?

Viele Grüße, Euklid

[af0815]

Kennt jemand was einfacheres bzw. schnelleres?

Suchen würde ich unter"parity", "even" oder "odd"Funktionen. Bei RS 232 Schnittstellen ist es implementiert. Leider kann ich mehr nicht sagen, da die Artikel mir sofort zu abstract mathematisch werden

Vielleicht Info hier: Diskussion über Parity

[mse]

Mittels Tabelle byteweise oder wortweise (etwas grössere Tabelle).

Code: Alles auswählen

const
 bitcounttab:  array[byte] of byte =
  //000 001 010 011 100 101 110 111
 (  0,  1,  1,  2,  1,  2,  2,  3,    //0000 0xxx   0
    0+1,1+1,1+1,2+1,1+1,2+1,2+1,3+1,  //0000 1xxx   1
    0+1,1+1,1+1,2+1,1+1,2+1,2+1,3+1,  //0001 0xxx   1
    0+2,1+2,1+2,2+2,1+2,2+2,2+2,3+2,  //0001 1xxx   2
    0+1,1+1,1+1,2+1,1+1,2+1,2+1,3+1,  //0010 0xxx   1
    0+2,1+2,1+2,2+2,1+2,2+2,2+2,3+2,  //0010 1xxx   2
    0+2,1+2,1+2,2+2,1+2,2+2,2+2,3+2,  //0011 0xxx   2
    0+3,1+3,1+3,2+3,1+3,2+3,2+3,3+3,  //0011 1xxx   3
    0+1,1+1,1+1,2+1,1+1,2+1,2+1,3+1,  //0100 0xxx   1
    0+2,1+2,1+2,2+2,1+2,2+2,2+2,3+2,  //0100 1xxx   2
    0+2,1+2,1+2,2+2,1+2,2+2,2+2,3+2,  //0101 0xxx   2
    0+3,1+3,1+3,2+3,1+3,2+3,2+3,3+3,  //0101 1xxx   3
    0+2,1+2,1+2,2+2,1+2,2+2,2+2,3+2,  //0110 0xxx   2
    0+3,1+3,1+3,2+3,1+3,2+3,2+3,3+3,  //0110 1xxx   3
    0+3,1+3,1+3,2+3,1+3,2+3,2+3,3+3,  //0111 0xxx   3
    0+4,1+4,1+4,2+4,1+4,2+4,2+4,3+4,  //0111 1xxx   4
    0+1,1+1,1+1,2+1,1+1,2+1,2+1,3+1,  //1000 0xxx   1
    0+2,1+2,1+2,2+2,1+2,2+2,2+2,3+2,  //1000 1xxx   2
    0+2,1+2,1+2,2+2,1+2,2+2,2+2,3+2,  //1001 0xxx   2
    0+3,1+3,1+3,2+3,1+3,2+3,2+3,3+3,  //1001 1xxx   3
    0+2,1+2,1+2,2+2,1+2,2+2,2+2,3+2,  //1010 0xxx   2
    0+3,1+3,1+3,2+3,1+3,2+3,2+3,3+3,  //1010 1xxx   3
    0+3,1+3,1+3,2+3,1+3,2+3,2+3,3+3,  //1011 0xxx   3
    0+4,1+4,1+4,2+4,1+4,2+4,2+4,3+4,  //1011 1xxx   4
    0+2,1+2,1+2,2+2,1+2,2+2,2+2,3+2,  //1100 0xxx   2
    0+3,1+3,1+3,2+3,1+3,2+3,2+3,3+3,  //1100 1xxx   3
    0+3,1+3,1+3,2+3,1+3,2+3,2+3,3+3,  //1101 0xxx   3
    0+4,1+4,1+4,2+4,1+4,2+4,2+4,3+4,  //1101 1xxx   4
    0+3,1+3,1+3,2+3,1+3,2+3,2+3,3+3,  //1110 0xxx   3
    0+4,1+4,1+4,2+4,1+4,2+4,2+4,3+4,  //1110 1xxx   4
    0+4,1+4,1+4,2+4,1+4,2+4,2+4,3+4,  //1111 0xxx   4
    0+5,1+5,1+5,2+5,1+5,2+5,2+5,3+5); //1111 1xxx   5
 
function bitcount(const number: integer): integer;
type
 integerbytesty = array[0..3] of byte;
begin
 result:= bitcounttab[integerbytesty(number)[0]] +
          bitcounttab[integerbytesty(number)[1]] +
          bitcounttab[integerbytesty(number)[2]] +
          bitcounttab[integerbytesty(number)[3]];
end;

[monta]

Aber Parität gibt ja nicht die Anzahl an, sondern nur, ob gerade oder ungerade zur Fehlererkennung.
Das wäre ja nur nen einfaches XOR über alle Stellen und gibt am Ende nur entweder 1 oder 0 zurück (bspw. als Prüfbit)

Aber wie ich Euklid verstehe, ist das ja nicht das Ziel.

@Euklid du willst also bei Gegebener Zahl, bspw.
01000011
Die Rückgabe 3 da drei mal die Eins vorkommt, hab ich dich da richtig verstanden?

[Socke]

Aber Parität gibt ja nicht die Anzahl an, sondern nur, ob gerade oder ungerade zur Fehlererkennung.
Das wäre ja nur nen einfaches XOR über alle Stellen und gibt am Ende nur entweder 1 oder 0 zurück (bspw. als Prüfbit)

Aber wie ich Euklid verstehe, ist das ja nicht das Ziel.

@Euklid du willst also bei Gegebener Zahl, bspw.
01000011
Die Rückgabe 3 da drei mal die Eins vorkommt, hab ich dich da richtig verstanden?

Genau so habe ich das auch verstanden.

Im Endeffekt habe gibt es dazu doch nur eine Hand voll Möglichkeiten:
1. Du musst über alle Bits iterieren und deren Status abfragen und anhand dessen zählen. Das kann a) mit einer Schleife oder b) mit einer Rekursion erfolgen.
2. Beim überprüfen kannst Du entweder
a) immer das letzte Bit überprüfen und danach alles um eins nach rechts shiften, oder
b) ohne zu shiften das der Schleifenzählvariablen entsprechnde Bit testen. Das kann a1) mittels shift ((1 shl i) and testzahl), oder a2) per Tabelle geschehen. CPU-seitig könnte ich mir vorstellen, dass a2) am schnellsten geht.
3. Ausrechnen. Wir wissen, welchen Wert wir haben und können also mit mod und div alles ausrechnen. Das dürfte aber zumindest im Quelltext schön bescheuert aussehen und über 1 oder 2 einfacher zu implementieren sein.

[Poelser]

b) ohne zu shiften das der Schleifenzählvariablen entsprechnde Bit testen. Das kann a1) mittels shift ((1 shl i) and testzahl), oder a2) per Tabelle geschehen. CPU-seitig könnte ich mir vorstellen, dass a2) am schnellsten geht.

Tabelle ist sicher am schnellsten, aber das kann man auch selbst implementieren:

1. Tabelle mit 256 Werten for 00000000 bis 11111111 erstellen (also für ein Byte)
2. Anzahl Bits 0 setzen
3. Schleife über die die einzelnen Bytes:
3a. Wert aus Tabelle holen
3b. Wert zu Anzahl Bits addieren

Noch schneller ginge es mit einem Word, nur braucht's dann 'ne Tabelle mit 65536 Werte in der Tabelle.

Zur Vorberechnung der Tabelle kann man natürlich wie von Socke vorgeschlagen die Einzelwerte berechnen. Oder natürlich speichern, also einmalig erzeugen, und nur laden, oder in den Quellcode in einem statischen vorbelegten Array vorhalten.

CU, der Poelser

[Euklid]

@Euklid du willst also bei Gegebener Zahl, bspw.
01000011
Die Rückgabe 3 da drei mal die Eins vorkommt, hab ich dich da richtig verstanden?

Ja genau

Danke Euch für Eure Antworten! Ich glaube, die Methode mit dem Shift wäre in diesem Fall die schnellste, da die Anwendung zudem (was ich oben vergessen habe zu erwähnen) speicherlastig ist...
... und shifts macht die CPU ja in einem Takt.

Viele Grüße, Euklid

[Socke]

... und shifts macht die CPU ja in einem Takt.

Gibt es eigentlich irgendwo Literatur darüber, wie lange (Taktzyklen) ein Prozessor für einen bestimmten Befehl benötigt?

[slai]

afaik macht man laufzeitabschätzungen von algorithmen mit der big-Oh Notation, sprich big-Omega und big-Theta.

[Socke]

afaik macht man laufzeitabschätzungen von algorithmen mit der big-Oh Notation, sprich big-Omega und big-Theta.

Naja, es ging mir eher darum, dass irgendwo in einer Delphi-Hilfe stand, dass eine Compiler-Optimierung sein könnte, dass Schleifen rückwärtslaufen (also von hohen Werten zu niedrigen) und mich interessieren würde, ob eine Subtraktion wirklich schneller ist als eine Addition (beides mal um 1).

[mse]

... mich interessieren würde, ob eine Subtraktion wirklich schneller ist als eine Addition (beides mal um 1).

Der Test auf Null am Ende der Schlaufe ist schneller als der Test auf einen bestimmten Endwert. Nach der Subtraktion von 1 muss lediglich das zero flag im bedingten Sprung ausgewertet werden.

[Socke]

Der Test auf Null am Ende der Schlaufe ist schneller als der Test auf einen bestimmten Endwert. Nach der Subtraktion von 1 muss lediglich das zero flag im bedingten Sprung ausgewertet werden.

Aah, danke...

[Euklid]

Naja, es ging mir eher darum, dass irgendwo in einer Delphi-Hilfe stand, dass eine Compiler-Optimierung sein könnte, dass Schleifen rückwärtslaufen (also von hohen Werten zu niedrigen) und mich interessieren würde, ob eine Subtraktion wirklich schneller ist als eine Addition (beides mal um 1).

Das spielte bei älteren Prozessoren mal eine Rolle. Seitdem man aus physikalischen Gründen nicht mehr sonderlich viel an der Takt-Schraube drehen kann, wurden die Prozessoren derart optimiert, dass sie pro Befehl nur noch sehr wenige Taktzyklen benötigen. Aktuelle Prozessoren sollten bei beinahe allen häufig benutzten Befehlen kaum mehr als 1 Zyklus benötigen - d.h. solche Optimierungen, wie du sie genannt hast und wie sie früher notwendig waren, bringen heute nichts mehr.

[monta]

INC und DEC sind ja an sich auch gleich schnell. Also die reine Addition macht zur Subtraktion ohnehin keinen Unterschied.

Die Frage ist ja höchstens, wie man dann den Vergleichswert "herzaubert".

Aber dank Pipelining und Sprungvorhersage dürfte sich da auch nichts spürbar unterscheiden. Wie Euklid schon schreibt, es lohnt sich meistens nicht.