Logarithmus Integerwert

gigg

Hallo,

ich suche nach einer Methode, schnell festzustellen, ob ein Integerwert x eine Potenz von 2 ist.
Die log2-Funktion aus math.h arbeitet ja nur mit Fließkommazahlen. Ein cast von x nach double und
anschließendes Überprüfen des Nachkommateils des Ergebnisses erscheint mir zu umständlich, letzlich
möchte ich nur wissen, ob in x nur 1 Bit gesetzt ist. Aber ich habe auch keine Idee, das Ganze
mit logischen bitweisen Verknüpfungen zu realisieren. Falls jemandem ein guter Ansatz einfällt, wäre
ich dankbar für eine Antwort.

Grüße

SG1

https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2

gigg

Super! Genau so etwas habe ich gesucht.

Danke

Finnegan

Noch eine Anmerkung: CPUs haben oft spezielle Instruktionen für diese Operation. Wenns du es also wirklich flott haben möchtest, lohnt es sich eventuell
mal die Compiler-Instrinsics __builtin_clz() / __builtin_clzll() (GCC/Clang) bzw. _BitScanReverse() / _BitScanReverse64() (MSVC) anzuschauen.

Ansonsten läuft die Integer-log₂-Funktion generell darauf hinaus das höchstwertigste 1-Bit zu finden. Der naive Ansatz sucht also einfach nur Bit für Bit
vom höchsten bis zum niedrigsten Bit, bis eine 1 gefunden wurde. Verblüffenderweise ist das auch der schnellste Algorithmus mit amortisiert O(1) für
beliebige n -bittige Zahlen - allerdings nur dann, wenn jede der 2ⁿ Bit-Kombinationen mit gleicher Wahrscheinlichkeit auftritt. In der Praxis testet man
meist jedoch Zahlen, bei denen höherwertigen Bits eher 0 sind (z.B. irgendwelche Objektgrössen, die ein size_t zur selten zur Gänze ausschöpfen),
so dass ich für eine Eigenimplementation eher zu einer Variante ähnlich einer binäre Suche raten würde (glaube diese hier auf der von SG1 verlinkten Seite).

gigg

@Finnegan

Danke dir für deine Antwort. Der erste Ansatz passt schon ganz gut. Damit bleibe ich CPU-unabhängig und die Geschwindigkeit ist für meine Zwecke voll ausreichend.
Mit der von SG1 verlinkten Seite werde ich mich noch weiter beschäftigen. Sehr interessant.

Grüße