Frage zu modulo 2/Bitwise &
-
Hallo,
ich lese dauernd, dass die Prüfung, ob eine Zahl gerade/ungerade ist, über den modulo Operator laufen solltemplate<typename T> inline bool IsEven(const T zahl) { return !(zahl%2); }Ich lese aber auch, dass der modulo Operator (relativ) langsam ist. Warum wählt man also nicht folgende Variante?
template<typename T> inline bool IsEven(const T zahl) { return !(zahl&1); }Wegen der Portabilität (sollte ja nur bei Big-Endian funktionieren)? Weil es nur auf POD's anwendbar ist? Oder optimiert der Compiler das eh weg?
In b4: Bitte keine "Premature Optimization" Flames" :p
-
Erklär doch kurz die Idee dahinter ...
-
&1 sollte schneller sein als %2 . . .
-
Also mein Programm verbringt 80% der Zeit mit IsEven Prüfungen. :p
-
Wird doch eh optimier0rt.
-
Wenn's um Geschwindigkeit geht: Ausprobieren. Ich würde vermuten, dass es keinen Unterschied macht. Eventuell wird sogar -- nach Optimierungsphase im Compiler -- der selbe Assembler-Code generiert. (Ich habe es nicht getestet).
Es gibt aber auch noch einen Unterschied bzgl Portabilität. "!(x % 2)" funktioniert immer auf allen möglichen Ganzzahltypen. Der Ausdruck ist unabhängig von der Art der Repräsentierung der Ganzzahlen. "!(x & 1)" kann das falsche Ergebnis liefern. Das ist dann der Fall, wenn der Compiler bzw der Rechner für vorzeichenbehaftete Ganzzahlen das 1er Komplement benutzt. Der Effekt der Bitoperationen auf vorzeichenbehaftete Ganzzahltypen hängt ab von der Repräsentierung der Zahlen, welche offiziell nicht auf das 2er Komplement beschränkt ist.
Also:
1. Compiler-Optimierungen einschalten
2. Prüfen, ob es wirklich einen Unterschied macht
3. Falls !(x & 1) schneller ist, stelle sicher, dass !(x & 1) entweder zum richtigen Ergebnis führt, oder sich der Code nicht kompilieren lässt -- zB über ein Modultest als Teil des Build-Prozesses.Gruß,
SP
-
Sebastian Pizer schrieb:
Das ist dann der Fall, wenn der Compiler bzw der Rechner für vorzeichenbehaftete Ganzzahlen das 1er Komplement benutzt.
Kennst Du geräte, die das tun, oder ist die Äußerung nur Quatsch?
-
für unsigned integertypen ist der entstehende assemblercode stets identisch. also schreib defensiv %2 und benutze keine signed typen, wenn du willst, daß der compiler bitfrickelt.
für signed typen habe ich schon unterschiede gesehen, wo &1 schneller war.
-
Okay, also wenn ich mich auf unsigned POD's beschränke, ist &1 protabel.
Aber wie sieht es mit Litte-/Big Endian aus? Hat das Auswirkungen?
-
Wieso sollte es? In welchem Byte das niederwertigste Bit steht, ist doch egal, solange es für beide Zahlen gleich ist.
-
volkard schrieb:
Sebastian Pizer schrieb:
[...] 1er Komplement [...]
Kennst Du geräte, die das tun, oder ist die Äußerung nur Quatsch?
Weder noch. Ich schätze, es gibt immer noch ein paar Exoten (alte Mainframes?), die nicht das 2er-Komplement benutzen. Wenn dem nicht so wäre, könnte man ja einfach in der nächsten Version der C und C++ Standards das 2er-Komplement erzwingen. Auch in dem neusten C++0x Entwurf gibt es §3.9.1/7:
Types bool, char, char16_t, char32_t, wchar_t, and the signed and unsigned integer types are collectively called integral types. A synonym for integral type is integer type. The representations of integral types shall define values by use of a pure binary numeration system. [ Example: this International Standard permits 2’s complement, 1’s complement and signed magnitude representations for integral types. — end example ]
Das erklärt dann auch, warum beispielsweise -127 für SCHAR_MIN erlaubt ist.
Gruß,
SP