Schnell Art und Weise zu überprüfen, ob eine ganze Zahl 2^n-mal eine andere ganze Zahl ist

Question

Gegeben seien zwei streng positive ganze Zahlen x und y in der Basis 2 ausgedrückt, gibt es eine schnelle Möglichkeit, zu überprüfen, ob x = 2^ny wo n ist eine ganze Zahl? (Das ist das gleiche wie die Überprüfung, ob x eine verschobene Version von ist y, aber ich bin nicht sicher, ob dies tatsächlich einfacher ist.)

Eine Lösung besteht darin zu prüfen, ob x% y = 0 und dass x/y ist eine Zweierpotenz (die sehr effizient durchgeführt werden kann [1]), aber dies erfordert einen Modulo und eine Division, zwei teure Operationen, sogar auf modernen Architekturen.

[1] x ist eine Zweierpotenz, wenn und nur wenn (x & (x - 1)) = 0

Answer 1

Die Modulo und Division könnten in die gleiche Operation verschmolzen werden, aber es wäre immer noch langsam. Ein anderer Ansatz ist, wie Sie erwähnen, versuchen einige n 's. Welche n ist? Sie können eine binäre Suche durchführen. Dies ist natürlich auch langsam. Ob es schneller oder langsamer als der erste Ansatz ist, naja, wer weiß. Kommt darauf an, wie schnell die Division für einen ist, der nicht auf jedem Prozessor gleich ist.

Wenn Sie ein numberOfTrailingZeros primitive haben (aka tzcnt oder fast gleichwertig ffs oder _BitscanForward) Sie x und y wie folgt normalisieren kann:

int nx = x >> tzcnt(x); 
int ny = y >> tzcnt(y); 

Dann, wenn nx == ny ist x eine Potenz von zwei mehrere von y, aber es könnte eine negative Macht von zwei sein, also müssen Sie auch überprüfen, dass tzcnt(x) >= tzcnt(y).

edit: Ich vermute, überprüfen, ob x >= y ist genug, um diesen Fall zu fangen.

Answer 2

Wenn Sie sich über die übermäßige Anstrengung von Division und Modulus-Operationen beklagen, dann verschieben Sie einfach die Bitmuster und vergleichen Sie sie. Das ist am einfachsten. Unter der Annahme von 64-Bit-Ganzzahlen und unter der Annahme einer gleichmäßigen Verteilung (was wahrscheinlich ungültig ist) würde es einen Durchschnitt von 32 Verschiebungs- und Vergleichsiterationen benötigen, um diesen Test durchzuführen. Ob 32-mal verschoben und verglichen wird, ist schneller als eine ganzzahlige Division und zwei Subtraktionen und ANDs sind zweifelhaft. Überprüfen Sie das Prozessorhandbuch, wenn Sie unsicher sind.