Identifizieren ungerade, gerade zahlen - Binär-vs. mod

Kürzlich musste ich erkennen, ob eine Zahl gerade oder ungerade ist, für eine große Anzahl von ganzen zahlen. Ich dachte, von einer Idee zu identifizieren, die eine Zahl als gerade oder ungerade durch UND ing es gegen 1 und vergleichen Sie das Ergebnis mit 1 

x & 1 == 1 //even or odd

Habe ich noch nie gesehen, diese Umsetzung in die Praxis. Der häufigste Weg, Sie immer zu sehen ist :

x % 2 == 0

Ich beschlossen, einige performance-check auf beide Methoden und die binäre Methode scheint etwas schneller auf meinem Rechner. 

int size = 60000000;
List<int> numberList = new List<int>();
Random rnd = new Random();

for (int index = 0; index < size; index++)
{
    numberList.Add(rnd.Next(size));
}

DateTime start;
bool even;

//regular mod
start = DateTime.Now;
for (int index = 0; index < size; index++)
{
    even = (numberList[index] % 2 == 0);
}
Console.WriteLine("Regualr mod : {0}", DateTime.Now.Subtract(start).Ticks);

//binary 
start = DateTime.Now;
for (int index = 0; index < size; index++)
{
    even = ((numberList[index] & 1) != 1);
}
Console.WriteLine("Binary operation: {0}", DateTime.Now.Subtract(start).Ticks);

Console.ReadKey();

Hat jemand gesehen der binären Methode implementiert ? Irgendwelche Nachteile ?

InformationsquelleAutor der Frage Ender | 2010-10-11

  1. 19

    Gut, ja, es ist eine leichte Optimierung. Dieses code-snippet:

            uint ix = 3; //uint.Parse(Console.ReadLine());
        bool even = ix % 2 == 0;

    erzeugt diese Maschine code in der release-build:

                uint ix = 3;
0000003c  mov         dword ptr [ebp-40h],3 
            bool even = ix % 2 == 0;
00000043  mov         eax,dword ptr [ebp-40h] 
00000046  and         eax,1 
00000049  test        eax,eax 
0000004b  sete        al   
0000004e  movzx       eax,al 
00000051  mov         dword ptr [ebp-44h],eax

    Tun, beachten Sie, dass der JIT-compiler ist intelligent genug, um zu verwenden, UND die Prozessor-Anweisung. Es ist nicht eine Abteilung, wie der % - operator normalerweise durchführen. Ein dickes Lob gibt.

    Aber dein custom test (benutzerdefinierter test erzeugt mit diesem code:

            uint ix = uint.Parse(Console.ReadLine());
//Bunch of machine code
        bool even = (ix & 1) == 0;
00000024  test        eax,1 
00000029  sete        al   
0000002c  movzx       eax,al 
0000002f  mov         esi,eax

    Musste ich die Belegung Aussage, weil der JIT-compiler habe plötzlich smart und bewertet den Ausdruck zur compile-Zeit. Der code ist sehr ähnlich, aber der UND-Anweisung ersetzt wurde durch eine TEST-Anweisung. Speichern Unterricht in den Prozess. Ziemlich ironisch, wie es dieses mal wählte nicht Verwendung eines UND -:)

    Diese sind die fallen Annahmen zu machen. Ihre ursprüngliche Instinkt war richtig, es sollte jedoch zu speichern, etwa eine halbe Nanosekunde. Sehr schwer zu sehen, dass zurück, es sei denn, dieser code lebt in einer sehr engen Schleife. Es wird drastisch anders, wenn Sie ändern die variable uint nach int, der JIT-compiler erzeugt dann code, der versucht, schlau zu sein, das Vorzeichen-bit. Unnötig.

    InformationsquelleAutor der Antwort Hans Passant

  2. 4

    Für solche Operationen sollten Sie lieber die mehr lesbar Ansatz (meiner Meinung nach die modulo-Weg) über die eine, die dachte schneller zu sein.

    Darüber hinaus die modulo-operation oben kann optimiert werden durch den compiler in die bitweisen und-operation. Daher braucht man eigentlich nicht zu kümmern.

    Anmerkung zu deinem Beispiel: mehr-präzise Ergebnisse prüfen, übergeben Sie die Anzahl der Elemente Hinzugefügt werden, die in der Liste der Konstruktor. So vermeiden Sie Unstimmigkeiten eingeführt, die von mehreren Umverteilung der backing-array. Für 60 Millionen integer-Elemente (ca. 240 MB Speicher) nicht preallocating der Erinnerung darstellen können, ist eine deutliche Verzerrung.

    InformationsquelleAutor der Antwort Ondrej Tucny

  3. 3

    Diese Webseite benchmarks mindestens ein halbes Dutzend Möglichkeiten, um festzustellen, ob eine Zahl gerade oder ungerade ist.

    War der Schnellste (die ich wie für einfache Lesbarkeit):

    if (x % 2 == 0)
    //even number
else
    //odd number

    Hier waren andere getestet (code ist hier). Ich bin wirklich überrascht, die bitweise und-Verknüpfung bit-Verschiebung Operationen nicht die besten:

    //bitwise
if ((x & 1) == 0)
    //even number
else
    //odd number


System.Math.DivRem((long)x, (long)2, out outvalue);
if ( outvalue == 0)
    //even number
else
    //odd number


if (((x / 2) * 2) == x)
    //even number
else
    //odd number


//bit shifting
if (((x >> 1) << 1) == x)
    //even number
else
    //odd number


index = NumberOfNumbers;
while (index > 1)
    index -= 2;
if (index == 0)
    //even number
else
    //odd number


tempstr = x.ToString();
index = tempstr.Length - 1;
//this assumes base 10
if (tempstr[index] == '0' || tempstr[index] == '2' || tempstr[index] == '4' || tempstr[index] == '6' || tempstr[index] == '8')
    //even number
else
    //odd number

    InformationsquelleAutor der Antwort Thrawn Wannabe

  4. 2

    Bitweise und schlagen modulo-division an jedem Tag der Woche. Division durch eine beliebige Anzahl nimmt eine Menge der Taktzyklen, während die bitweise und-Verknüpfung ist ein wesentlicher primitive op, die fast immer abgeschlossen, die in 1 Taktzyklus, unabhängig von Ihrer CPU-Architektur.

    Was Sie möglicherweise zu sehen, obwohl, ist, dass die compiler können den Austausch x mod 2 mit einer bit-Verschiebung oder eine bit-Maske, die Instruktion, die haben identische Leistung zu Ihrem eigenen bit-Maske-Betrieb.

    Um zu bestätigen, dass der compiler spielen tricks mit dem code, vergleichen Sie die Leistung von x mod 2 x mod 7 oder jeder anderen non-base 2 integer. Oder verdecken die Operanden aus dem compiler, so dass Sie nicht führen Sie die Optimierung:

    var y = 2;
result = x mod y;

    Wenn Sie sehen einen dramatischen Unterschied in der Ausführungszeit, mit diesen änderungen, dann ist das ein ziemlich starkes Indiz dafür, dass der compiler die Behandlung von x mod 2 als ein besonderer Fall und nicht mit der division zu finden, der Rest.

    Und wenn Sie DateTime-benchmark single instruction operations, stellen Sie sicher, Sie haben eine ausreichend lange Schleife, die die Prüfung läuft mindestens 5 Minuten oder so, um Ihre wahre Messung über dem Grundrauschen.

    InformationsquelleAutor der Antwort dthorpe

  5. 0

    Wäre das nicht der binären Methode schneller sein, weil der compiler in der Lage ist, um dies zu optimieren, in einem bitshift statt tatsächlich zwingt die cpu, um die Teilung Berechnung?

    InformationsquelleAutor der Antwort DJ Quimby

  6. 0

    Ich Stimme mit den anderen Antworten, dass Sie verwenden sollten, die modulo überprüfen, weil es am besten vermittelt Absicht.

    Jedoch für Ihre konkreten Ergebnisse; versuchen Sie es mit der even variable. Es wird einen signifikanten Unterschied machen, weil der compiler könnte in der Tat optimieren entfernt einige der Berechnungen, weil es weiß, dass es nicht erforderlich ist, verwenden Sie den Wert.

    Mit Ihrem Programm (modifiziert nach Einsatz Stoppuhr), bekomme ich 70 ms für den regulären mod und 88 ms für die binäre operation. Wenn ich die even variable, der Unterschied ist viel kleiner (327 vs-316 ms), und die modulos ist am schnellsten.

    InformationsquelleAutor der Antwort driis

  7. 0

    Für vorzeichenlose zahlen, viele Compiler optimieren wird, der 'mod' - operator als 'und' test. Für vorzeichenbehaftete zahlen, (x % 2) 1, wenn die Zahl ist ungerade und positiv ist; -1, wenn es ungerade ist, und negativ, obwohl beide +1 und -1 sind ungleich null, Sie erhalten möglicherweise nicht als gleichwertig anerkannt.

    BTW, bei Verwendung der "und" - operator, würde ich testen !=0 statt ==1. Compiler kann erkennen die Gleichwertigkeit, aber Sie kann nicht.

    InformationsquelleAutor der Antwort supercat

Schreibe einen Kommentar