wake-up-neo.net

Wie kann man überprüfen, ob die angegebene Anzahl auf schnellste Weise von 15 teilbar ist?

Die Aufteilung in den Prozessor ist sehr zeitaufwändig, daher möchte ich fragen, wie man am schnellsten eincheckt, ob die Zahl von einer anderen Zahl teilbar ist. In meinem Fall muss ich prüfen, ob die Zahl durch 15 teilbar ist.

Ich habe auch durch das Web geschaut und habe fun gefunden, um zu überprüfen, ob die Anzahl von einer Anzahl teilbar ist, aber ich suche nach einer schnellen Option.

HINWEIS: Da die Division viel Zeit in Anspruch nimmt, suche ich nach Antwort ohne / und %.

17
user2532605

Die Multiplikation erfordert weniger Zeit als die Division, daher können Sie Folgendes versuchen:

inline bool divisible15(unsigned int x)
{
    //286331153 = (2^32 - 1) / 15
    //4008636143 = (2^32) - 286331153
    return x * 4008636143u <= 286331153u;
}

Dieser Weg funktioniert, weil 2^32-1 (maximaler 32-Bit-Wert) von 15 teilbar ist. Wenn Sie jedoch beispielsweise 7 verwenden, würde es aussehen, als würde es funktionieren, aber es würde nicht in allen Fällen funktionieren.

EDIT: Siehe this , es beweist, dass diese Lösung (auf einigen Compilern) schneller ist als das Modul.

EDIT:Hier ist die Erklärung und die Verallgemeinerung.

24
ST3

Obligatorische Antwort für andere Lernende, die nach einer Antwort suchen.

if (number % n == 0)

In den meisten Fällen können Sie dies immer tun, indem Sie den intelligenten modernen Compilern vertrauen.

Dies bedeutet jedoch nicht, dass Sie vom Lernen auf unterhaltsame Weise entmutigt werden. Schauen Sie sich diese Links an.

Schnelle Teilbarkeitstests (nach 2,3,4,5, .., 16)?

Bit Twiddling Hacks

31
Max

Verwenden Sie einfach i % 15 == 0 


  1. Da der Compiler leicht erkennen kann, dass 15 sich niemals ändern wird, kann er sich frei für die Optimierung der Mod-Operation entscheiden. Es ist eine Aufgabe des Compilerschreibers, diese Art der Optimierung durchzuführen, wenn sie sich keine bessere Art und Weise überlegt haben. 

  2. Zum Beispiel ist es sehr einfach zu prüfen, ob eine Zahl durch 2 teilbar ist, weil Sie nur das erste Bit prüfen. Compiler-Schreiber wissen das und Sie könnten den Code selbst schreiben, um das erste Bit zu überprüfen, aber besonders bei einem ausgereiften Compiler werden die Leute jahrelang über diese Dinge nachdenken und daran arbeiten. Diese Art der Optimierung ist sehr einfach durchzuführen, da nur eine Anweisung oder 2 geändert werden muss. Optimierungen wie eine bessere Registerbelegung sind viel schwieriger zu erreichen 

  3. Zu beachten ist noch, dass Ihr Compiler für das System geschrieben wurde, auf dem er läuft, Ihr Code hingegen ist überall gleich, wenn Sie einen merkwürdigen Code schreiben, der auf einem System möglicherweise genauso schnell ist (wahrscheinlich noch nicht schneller) ) aber auf einem anderen System, das über eine spezielle Hardwareoptimierung verfügt, kann Ihr Code um eine Größenordnung verlieren. Da Sie etwas esoterischen Code geschrieben haben, um die Teilbarkeit zu prüfen, ist es unwahrscheinlich, dass der Compiler zu einer einzigen Hardwareoperation optimieren kann. Das Schreiben des Offensichtlichen zu tun macht das Leben für Sie besser und für den Compiler einfacher. 

  4. Da Sie nicht wirklich überprüft haben, dass die Geschwindigkeit beim Schreiben von Code von Bedeutung ist, wird der Code für die nächste Person sehr schwer lesbar und fehleranfälliger ( vorzeitige Optimierung ist die Wurzel allen Übels

  5. Es funktioniert immer noch, ob die Eingabe 16, 32 oder 64 Bit ist, da keine Bitmanipulation erforderlich ist. 

  6. Selbst wenn der Compiler-Writer es nicht implementiert hat, ist es durchaus möglich, dass jemand es implementiert (auch Sie selbst).

24
aaronman

Bei einem relativ modernen Prozess sollte die Teilung durch 15 nicht so schlimm sein. Der AMD-Optimierungsleitfaden definiert sie basierend auf dem Quotienten (dem Wert, der geteilt wird) und nimmt eine 8 + Bit-Position des höchstwertigen Bits des Quotienten ein. Wenn also für Ihre Zahlen das 63. Bit eingestellt ist, erhalten Sie 71 Zyklen - was natürlich eine recht lange Anweisung ist. Bei einer 32-Bit-Zahl mit einigen Nullen in den oberen Bits handelt es sich um 30-40 Zyklen. Wenn die Anzahl in einen 16-Bit-Wert passt, beträgt das Maximum 23 Zyklen. 

Für den Rest gibt es noch einen weiteren Taktzyklus. 

Wenn Sie dies zu jeder Zeit tun, stellen Sie möglicherweise fest, dass diese Zeit ziemlich lang ist, aber ich bin nicht sicher, ob es einen trivialen Weg gibt, um dies zu vermeiden. 

Wie andere schon gesagt haben, kann der Compiler ihn durch etwas Besseres ersetzen. Aber 15 hat meines Wissens keine offensichtliche schnelle Lösung (wenn Sie 16 anstelle von 15 haben, können wir den Trick von x & 15 verwenden). 

Wenn es sich um einen begrenzten Bereich handelt, können Sie beispielsweise eine Tabelle [vector<bool> erstellen, die 1 Bit pro Eintrag speichert], aber Sie werden schnell das Problem haben, dass der nicht zwischengespeicherte Speicherzugriff genauso lange dauert wie eine Divisionsoperation ...

Es gibt einige interessante Möglichkeiten, um herauszufinden, ob eine Zahl durch 3, 5 usw. dividiert, indem die Ziffern summiert werden. Leider funktionieren diese Zahlen nur auf Dezimalstellen, was eine lange Folge von Dividenden beinhaltet. 

6
Mats Petersson

Hier ist ein anderer Ansatz, der wahrscheinlich langsamer ist als andere, jedoch nur die Addition, bitweise und und verschiebt:

int divisible15(unsigned int x) {
        if (x==0) return 1;
        x = (x & 0x0f0f0f0f) + ((x&0xf0f0f0f0)>>4);
        x = (x & 0x00ff00ff) + ((x&0xff00ff00)>>8);
        x = (x & 0x0000ffff) + ((x&0xffff0000)>>16);
        x = (x & 0x0f) + ((x&0xf0)>>4);
        return x==15;
}

Die Idee ist, dass die Teilbarkeit durch 15 in der Basis 16 wie die Teilbarkeit durch 9 in der Basis 10 ist - die Summe der Ziffern muss durch 15 teilbar sein.
Der Code summiert also alle Hex-Ziffern zusammen (ähnlich wie Sie Bits zählen), und die Summe muss 15 sein (außer 0).

5
ugoren

Nun, es ist sehr einfach in Ihrem Kopf zu tun, wenn Sie die Hex-Darstellung haben. Addieren Sie einfach alle Ziffern, bis Sie eine einzige Ziffer haben. Wenn die Antwort "0xf" lautet, ist sie durch 15 teilbar. 

Beispiel 0x3a98: 3 + 0xa + 9 + 8 = 0x1e = 1 + 0xe = 0xf, also durch 15 teilbar.

Dies funktioniert für alle Faktoren in X-1, wobei X die Basis ist, die zur Darstellung der Zahl verwendet wird. (Bei kleineren Faktoren muss die letzte Ziffer durch den Faktor teilbar sein).

Erwarten Sie nicht, dass dies im Code schnell ist.

0
Roddy