Wie berechnet man Log2 für ganzzahlige Werte in C genau?

Korrekte Methode zur Berechnung von Log2 in C für Ganzzahlwerte

In C-Standardbibliotheken gibt es nur die Log-Methode für Gleitkommazahlen. Die Protokollmethode wird jedoch häufig verwendet, um die Ebene eines Index in einem Binärbaum mithilfe der Formel floor(2log(index)) zu ermitteln.

Ein gängiger Ansatz ist die Verwendung von int targetlevel = int(log(index)/log(2)). Dieser Ansatz kann jedoch zu Rundungsfehlern für Kantenelemente (Elemente mit dem Wert 2^n) führen, was dazu führt, dass n-1,999999999999 anstelle des erwarteten n,0 zurückgegeben wird.

Lösung für eine genaue Log2-Berechnung

Um dieses Problem zu beheben und eine genaue Log2-Berechnung für ganzzahlige Werte sicherzustellen, ist die Verwendung des BSR-Befehls (Bit Scan Reverse) ein besserer Ansatz. bsr ist auf x86- und x86-64-Plattformen verfügbar und gibt die Position des höchsten gesetzten Bits in einer vorzeichenlosen Ganzzahl zurück. Dies entspricht log2() für positive ganze Zahlen.

Hier ist ein optimierter C-Codeausschnitt, der die BSR-Anweisung nutzt:

#include <stdint.h>

static inline uint32_t log2(const uint32_t x) {
  uint32_t y;
  asm ( "\tbsr %1, %0\n"
      : "=r"(y)
      : "r" (x)
  );
  return y;
}

Dieser Code verwendet Inline-ASM, um die BSR-Anweisung effizient und effizient aufzurufen Bietet präzise log2-Berechnungen für ganze Zahlen.

Das obige ist der detaillierte Inhalt vonWie berechnet man Log2 für ganzzahlige Werte in C genau?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!