Wie findet man am schnellsten heraus, ob eine Zahl gerade oder ungerade ist?

Lesezeit: 5 Minuten

Benutzeravatar von aks
fragt

Wie findet man am schnellsten heraus, ob eine Zahl gerade oder ungerade ist?

  • Das ist eine gute Anfänger-C-Frage. +1 von mir.

    – t0mm13b

    9. Februar 2010 um 13:21 Uhr

  • Ist bitweises XOR nicht schneller als bitweises UND? Ist es nicht mit XOR-Operation möglich?

    – bitte

    9. Februar 2010 um 14:00 Uhr

  • @aks: Wenn Sie einen Compiler mit vollem Funktionsumfang verwenden, kennt dieses Backend diese Tricks mit ziemlicher Sicherheit besser als du. Schreiben Sie für Klarheit und Lesbarkeit und überlassen Sie die Bit-Fummelei, die Zyklusoptimierung dem Profi. Wirklich. Und wenn Sie mit den Ergebnissen nicht zufrieden sind, erstellen Sie ein Profil und untersuchen Sie die Hotspots im Detail.

    – dmckee — Ex-Moderator-Kätzchen

    9. Februar 2010 um 14:05 Uhr

  • @dmckee: Wie auch immer, ich würde gerne eine Lösung sehen, die nur eine einzige XOR-Anweisung verwendet. Ich glaube nicht, dass das möglich ist…

    – AndiDog

    9. Februar 2010 um 14:59 Uhr

  • Stellen Sie sicher, dass Sie dies vor der Mikrooptimierung gelesen haben: linux-kongress.org/2009/slides/…

    – mmx

    9. Februar 2010 um 15:16 Uhr

Das ist ziemlich bekannt

static inline int is_odd_A(int x) { return x & 1; }

ist effizienter als 

static inline int is_odd_B(int x) { return x % 2; }

Aber wenn der Optimierer eingeschaltet ist, wird is_odd_B nicht anders sein als is_odd_A? Nein – mit gcc-4.2 -O2erhalten wir (in der ARM-Assembly):

_is_odd_A:
    and r0, r0, #1
    bx  lr

_is_odd_B:
    mov r3, r0, lsr #31
    add r0, r0, r3
    and r0, r0, #1
    rsb r0, r3, r0
    bx  lr

Wir sehen das is_odd_B dauert 3 Anweisungen mehr als is_odd_Ader Hauptgrund ist, weil

((-1) % 2) == -1
((-1) & 1) ==  1

Jedochgenerieren alle folgenden Versionen denselben Code wie is_odd_A:

#include <stdbool.h>
static inline bool is_odd_D(int x) { return x % 2; }      // note the bool
static inline int  is_odd_E(int x) { return x % 2 != 0; } // note the !=

Was bedeutet das? Der Optimierer ist normalerweise so ausgeklügelt, dass er für diese einfachen Dinge Der klarste Code reicht aus, um die beste Effizienz zu gewährleisten.

  • noch besser, spezifizieren Sie das Argument als unsigned.

    – Kartoffelklatsche

    9. Februar 2010 um 18:59 Uhr

  • @Kartoffelwatter: x%2U oder x&1U. 🙂

    – R.. GitHub HÖR AUF, EIS ZU HELFEN

    21. September 2010 um 3:15 Uhr

  • was ist, wenn Sie 1 eingeben, es sagt ungerade

    – ichimaru

    5. September 2018 um 1:33 Uhr

  • x & 1 wird falsche Antworten auf seine Komplementsysteme geben. Für vollständig portierbaren Code, der auf den normalen Zweierkomplementsystemen, die uns wichtig sind, effizient kompiliert werden kann, müssen Sie entweder unsigned or verwenden x % 2 != 0

    – Peter Cordes

    12. Dezember 2018 um 4:51 Uhr

Benutzeravatar von AndiDog
AndiDog

Übliche Vorgehensweise:

int number = ...;
if(number % 2) { odd }
else { even }

Alternative:

int number = ...;
if(number & 1) { odd }
else { even }

Getestet auf GCC 3.3.1 und 4.3.2, beide haben ungefähr die gleiche Geschwindigkeit (ohne Compiler-Optimierung), da beide im Ergebnis resultieren and Anweisung (auf x86 kompiliert) – Ich weiß, dass die Verwendung der div Anweisungen für Modulo wären viel langsamer, daher habe ich es überhaupt nicht getestet.

  • Der Compiler hat den Test wahrscheinlich vollständig entfernt, da beide wahrscheinlich konstant sind. Erinnere dich daran gcc ohne Optionen ist gleichbedeutend mit gcc -O2 Dies ist eine nicht triviale Ebene der Geschwindigkeitsoptimierung. Überprüfen Sie die generierte Assembly, um sicherzugehen.

    – dmckee — Ex-Moderator-Kätzchen

    9. Februar 2010 um 13:46 Uhr

  • Ist bitweises XOR nicht schneller als bitweises AND? Ist es nicht mit XOR-Operation möglich?

    – bitte

    9. Februar 2010 um 14:00 Uhr

  • @dmckee: Ich weiß nicht, warum Sie denken, dass Level 2 die Standardeinstellung war. Die Manpage sagt eindeutig “-O0 Nicht optimieren. Dies ist die Standardeinstellung.”. Aber ich habe den Assembler-Code trotzdem überprüft und er wurde nicht aus dem Code entfernt (deshalb dauert es 7 Sekunden, bis jeder Test ausgeführt wird).

    – AndiDog

    9. Februar 2010 um 14:14 Uhr

  • @aks: Ich habe bitweises XOR getestet und es ist mit der gleichen Geschwindigkeit wie AND/Modulo (Übrigens erzeugen diese beiden denselben Code auf x86, nämlich eine “and” -Anweisung). Wie auch immer, könnten Sie mir sagen, wie ich ungerade/gerade mit bestimmen kann nur eine XOR-Anweisung?

    – AndiDog

    9. Februar 2010 um 14:16 Uhr

  • InRe-Optimierungsstufen: Mea Cupla.

    – dmckee — Ex-Moderator-Kätzchen

    9. Februar 2010 um 14:41 Uhr

wenn (x & 1) wahr ist, dann ist es ungerade, andernfalls ist es gerade.

  • Dies schlägt auf einer Maschine fehl, die das eigene Komplement verwendet.

    – Jason

    9. Februar 2010 um 14:25 Uhr

  • Außerdem, und dies ist ein allgemeiner Kommentar zu allen bisherigen Antworten, wurde in der Frage nicht angegeben, dass die Zahl eine ganze Zahl war. Sie können keine bitweisen Operationen mit Gleitkommazahlen durchführen (zumindest nicht ohne Typumwandlungs-Hacker).

    – Schizz

    9. Februar 2010 um 14:49 Uhr

  • @Skizz: Definiere gerade oder ungerade für eine Nicht-Ganzzahl.

    – dmckee — Ex-Moderator-Kätzchen

    9. Februar 2010 um 15:10 Uhr

  • @dmckee: float i=2.0f; // gerade Zahl! aber i&1 funktioniert nicht.

    – Schizz

    9. Februar 2010 um 19:55 Uhr

  • @Skizz Sie können es für 2.0 definieren Weil es hat einen ganzzahligen Ausdruck. Das Richtige ist also, in int zu konvertieren und das Ergebnis wie besprochen zu behandeln.

    – dmckee — Ex-Moderator-Kätzchen

    9. Februar 2010 um 20:24 Uhr 

bool is_odd = number & 1;


int i=5;
if ( i%2 == 0 )
{
   // Even
} else {
   // Odd
}

  • Das Prüfen des niederwertigsten Bits wäre schneller als der Modulo-Operator. Ich wette jedoch, dass die meisten Compiler “mod 2” in “and 1” umwandeln würden

    – Bramp

    9. Februar 2010 um 13:00 Uhr

  • @bramp: sie können nicht wenn i ist unterschrieben.

    – R.. GitHub HÖR AUF, EIS ZU HELFEN

    21. September 2010 um 3:17 Uhr

  • @R: Bist du sicher? Beispielsweise ist das Zweierkomplement von 127 “01111111” und -127 ist “10000001”, beide haben das niedrigstwertige Bit gesetzt.

    – Bramp

    21. September 2010 um 11:25 Uhr

Benutzeravatar von Maurits Rijk
Maurits Rijk

int is_odd(int n)
{
   if (n == 0)
      return 0;
   else if (n == 1)
      return 1;
   else
      return !is_odd(n - 1);
}

Oh warte, hast du gesagt am schnellsten übrigens nicht am lustigsten. Mein Fehler 😉

Die obige Funktion funktioniert natürlich nur für positive Zahlen.

  • Das Prüfen des niederwertigsten Bits wäre schneller als der Modulo-Operator. Ich wette jedoch, dass die meisten Compiler “mod 2” in “and 1” umwandeln würden

    – Bramp

    9. Februar 2010 um 13:00 Uhr

  • @bramp: sie können nicht wenn i ist unterschrieben.

    – R.. GitHub HÖR AUF, EIS ZU HELFEN

    21. September 2010 um 3:17 Uhr

  • @R: Bist du sicher? Beispielsweise ist das Zweierkomplement von 127 “01111111” und -127 ist “10000001”, beide haben das niedrigstwertige Bit gesetzt.

    – Bramp

    21. September 2010 um 11:25 Uhr

Überprüfen Sie, ob das letzte Bit 1 ist.

int is_odd(int num) {
  return num & 1;
}

  • Siehe den Kommentar von Tom, gleiches gilt hier. Dies wird nicht in C kompiliert.

    – AndiDog

    9. Februar 2010 um 14:22 Uhr

  • Richtig … geändert in int. (FWIW, einige Build-Umgebungen #define oder typedef bool to int).

    – 0xfe

    9. Februar 2010 um 14:54 Uhr

1412890cookie-checkWie findet man am schnellsten heraus, ob eine Zahl gerade oder ungerade ist?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy

Contact - Terms and Conditions - Privacy Policy