Das ist der beste Weg, in C, um zu sehen, ob eine Zahl ist teilbar durch eine andere?
Was ist der beste Weg, in C, um zu sehen, ob eine Zahl ist teilbar durch eine andere? Ich benutze diese:
if (!(a % x)) {
//this will be executed if a is divisible by x
}
Ist es trotzdem, welche ist schneller? Ich weiß, dass tun, ich.e, 130 % 13 führt das zu tun, 130 /13 pro 10 mal. Also es sind 10 Zyklen, wenn nur eine benötigt wird (ich will nur wissen ob 130 ist teilbar durch 13).
Dank!
- Ähm, Sie wissen das nicht, obwohl Sie denken vielleicht, es, zu Unrecht. Auf einem modernen Prozessor, der mod-operator wird in der Regel eine einzelne Maschinencode-Instruktion.
- Nit: d.h. bedeutet, grob gesagt, "das ist." Du meinst zu sagen z.B., was bedeutet, "zum Beispiel."
- "130 % 13 führt das zu tun, 130 / 13 je 10-mal" - warum würde Sie denken, dass?
- Und wieder einmal, wer in der Hölle ist die Abstimmung auf?
- Mit
!(a % b)
ist schlechter Stil, weil Sie den Umgang mit zahlen. Bessere Nutzunga % b == 0
. - Abstimmung zu schließen, zu lokalisieren.
- Mit
!
mit zahlen ist nicht schlechter Stil. Das ist C, nicht Java...
Du musst angemeldet sein, um einen Kommentar abzugeben.
Mumpitz.
%
keine solche Sache, die auf allen Prozessoren, die ich je benutzt habe. Es tut130/13
einmal, und gibt den Rest.Verwenden
%
. Wenn Ihre Anwendung läuft zu langsam, Profil und zu beheben, was zu langsam ist.Für zwei beliebige zahlen, der beste Weg, um zu überprüfen, ist zu prüfen, ob
a % b == 0
. Der modulo-operator hat unterschiedliche performance basiert auf der hardware, sondern mit dem compiler können dies herauszufinden, viel besser als Sie können. Der modulo-operator ist universell, und Ihre compiler herauszufinden, die beste Sequenz von Anweisungen zu emittieren, für welchen hardware Sie läuft.Wenn eine der zahlen ist eine Konstante, der compiler kann optimieren, indem Sie eine Kombination von bit-Verschiebungen und-Abzüge (meist für Potenzen von zwei), da die hardware div/mod ist langsamer als eine addition oder Subtraktion, aber auf modernen Prozessoren, die Wartezeit (schon nur ein paar Nanosekunden) verborgen ist durch Tonnen von anderen performance-tricks, also brauchen Sie nicht Sorge über es. Keine hardware berechnet-Modul durch wiederholte division (einige alte Prozessoren haben die division durch wiederholte bit-Verschiebungen und Subtraktion, aber Sie noch verwendet spezielle hardware für diese, damit noch schneller die hardware, die es tun, als zu versuchen, zu emulieren, in der software). Die meisten modernen ISAs tatsächlich berechnen beide division und Rest in einer Anweisung.
Die einzige Optimierung, die könnte nützlich sein wird, wenn der divisor ist eine Potenz von zwei. Dann können Sie
&
Maske die low-order bits (von Teiler - 1) und prüfen das Ergebnis gegen null. Zum Beispiel, um zu überprüfen, oba
ist durch 8 teilbar,a & 7 == 0
entspricht. Ein guter compiler wird dies für Sie tun, so bleiben Sie mit just-stick mit%
.Im Allgemeinen Fall mit Hilfe der modulo-operator ist wahrscheinlich die Schnellste Methode zur Verfügung. Es gibt Ausnahmen, besonders wenn Sie daran interessiert sind, ob zahlen sind teilbar durch Potenzen von zwei (in dem Fall bitweise Operationen stehen zur Verfügung), aber der compiler sollte wählen Sie automatisch für Sie, wenn Sie nur
%
. Sie sind kaum in der Lage, das zu tun besser für beliebige Werte wie13
.Außerdem, was meinst du mit "doing 130 /13 je 10-mal"? Es tut
130 /13
einmal. Das ist genau das, was erforderlich ist.Wenn
x
ist eine Konstante, dann ja:0x4ec4ec4ec4ec4ec5
ist die modulare multiplikative inverse 13 (modulo 264), so wenna
ist wirklich ein Vielfaches der 13, dann wird das Produkt weniger als (264/13). (Da ist 13 mal einige integern
, undn
muss passen in einen 64-bit-Wort, was bedeutet, dass es weniger als 264.)Dies funktioniert nur für ungerade Werte von
x
. Für die geraden zahlen (also ein Vielfaches von 2y für y>0) Sie können kombinieren Sie diesen test mit einer bitweisen UND-test (die letzteny
bitsa
sollte null sein. Wenn Sie sind, dann teilen Siea
von 2y und fahren Sie mit der Multiplikation zu testen.)Dies ist nur sinnvoll, wenn
x
ist eine Konstante, da das berechnen der multiplikativen inversen ist teurer als integer-division.Bearbeiten: ich bin auch davon
a
undx
sind unsigniert.(x % 13)
im GCC oder MSVC und du wirst sehen, ein Teil Ihrer Magie-Nummer (0x4ec4ec4e + 1
) so gut wie keine eigentliche division. Siehe stackoverflow.com/questions/2580680/... für weitere details.Wenn die Maschine
%
es nicht einfach eine Abteilung Unterricht, und generiert automatisch einen Rest.Jedoch, bewusst sein, dass, wenn eine der zahlen negativ ist, wird
%
geben einen negativen Rest.Wenn Sie nur über einen Rest von null, ist das kein problem,
aber wenn Sie gerade auf der Suche nach einem anderen Rest, wie 1, kann es wirklich Reise, die Sie bis.