Logarithmus Integerwert



  • 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





  • Super! Genau so etwas habe ich gesucht.

    Danke 🙂



  • 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-log2-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 2n 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).



  • @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


Anmelden zum Antworten