Schnelle Berechnung von log2 für 64-Bit-Ganzzahlen

Eine großartige Programmierressource, Bit Twddling Hacks, schlägt vor (hier) die folgende Methode, um log2 einer 32-Bit-Ganzzahl zu berechnen:

#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
static const char LogTable256[256] = 
{
    -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
    LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
    LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
};

unsigned int v; // 32-bit word to find the log of
unsigned r;     // r will be lg(v)
register unsigned int t, tt; // temporaries
if (tt = v >> 16)
{
    r = (t = tt >> 8) ? 24 + LogTable256
}
else 
{
    r = (t = v >> 8) ? 8 + LogTable256
}

und erwähnt das

Die Lookup-Table-Methode benötigt nur etwa 7 Operationen, um das Protokoll eines 32-Bit-Werts zu finden. Wenn es für 64-Bit-Mengen erweitert würde, würde es ungefähr 9 Operationen dauern.

gibt aber leider keine zusätzlichen Informationen darüber, welchen Weg man tatsächlich gehen sollte, um den Algorithmus auf 64-Bit-Ganzzahlen zu erweitern.

Irgendwelche Hinweise darauf, wie ein solcher 64-Bit-Algorithmus aussehen würde?

Intrinsische Funktionen sind wirklich schnell, aber für eine wirklich plattformübergreifende, Compiler-unabhängige Implementierung von log2 noch unzureichend. Falls es also jemanden interessiert, hier ist der schnellste, verzweigungsfreie, CPU-abstrakte DeBruijn-ähnliche Algorithmus, auf den ich bei meinen eigenen Recherchen zu diesem Thema gestoßen bin.

const int tab64[64] = {
    63,  0, 58,  1, 59, 47, 53,  2,
    60, 39, 48, 27, 54, 33, 42,  3,
    61, 51, 37, 40, 49, 18, 28, 20,
    55, 30, 34, 11, 43, 14, 22,  4,
    62, 57, 46, 52, 38, 26, 32, 41,
    50, 36, 17, 19, 29, 10, 13, 21,
    56, 45, 25, 31, 35, 16,  9, 12,
    44, 24, 15,  8, 23,  7,  6,  5};

int log2_64 (uint64_t value)
{
    value |= value >> 1;
    value |= value >> 2;
    value |= value >> 4;
    value |= value >> 8;
    value |= value >> 16;
    value |= value >> 32;
    return tab64[((uint64_t)((value - (value >> 1))*0x07EDD5E59A4E28C2)) >> 58];
}

Der Teil des Abrundens auf die nächstniedrigere Potenz von 2 wurde aus entnommen Potenz-von-2-Grenzen und der Teil, um die Anzahl der nachgestellten Nullen zu erhalten, wurde entnommen BitScan (das (bb & -bb) Code, um das Bit ganz rechts herauszuheben, das auf 1 gesetzt ist, was nicht benötigt wird, nachdem wir den Wert auf die nächste Potenz von 2 abgerundet haben).

Und die 32-Bit-Implementierung ist es übrigens

const int tab32[32] = {
     0,  9,  1, 10, 13, 21,  2, 29,
    11, 14, 16, 18, 22, 25,  3, 30,
     8, 12, 20, 28, 15, 17, 24,  7,
    19, 27, 23,  6, 26,  5,  4, 31};

int log2_32 (uint32_t value)
{
    value |= value >> 1;
    value |= value >> 2;
    value |= value >> 4;
    value |= value >> 8;
    value |= value >> 16;
    return tab32[(uint32_t)(value*0x07C4ACDD) >> 27];
}

Wie bei jeder anderen Berechnungsmethode erfordert log2, dass der Eingabewert größer als Null ist.

Wenn Sie GCC verwenden, ist eine Nachschlagetabelle in diesem Fall nicht erforderlich.

GCC bietet eine eingebaute Funktion, um die Anzahl der führenden Nullen zu bestimmen:

Eingebaute Funktion: int __builtin_clz (unsigned int x)

Gibt die Anzahl der führenden 0-Bits in x zurück, beginnend bei der höchstwertigen Bitposition. Wenn x 0 ist, ist das Ergebnis undefiniert.

Sie können also definieren:

#define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))

und es funktioniert für alle unsigned long long int. Das Ergebnis wird abgerundet.

Für x86 und AMD64 kompiliert GCC es zu a bsr Anweisung, daher ist die Lösung sehr schnell (viel schneller als Nachschlagetabellen).

Arbeitsbeispiel:

#include <stdio.h>

#define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))

int main(void) {
    unsigned long long input;
    while (scanf("%llu", &input) == 1) {
        printf("log(%llu) = %u\n", input, LOG2(input));
    }
    return 0;
}

Kompilierte Ausgabe: https://godbolt.org/z/16GnjszMs

Ich habe versucht zu konvertieren Ermitteln Sie die logarithmische Basis 2 einer N-Bit-Ganzzahl in O(lg(N))-Operationen mit Multiplizieren und Nachschlagen auf 64-Bit durch Brute Force der magischen Zahl. Unnötig zu erwähnen, dass es eine Weile gedauert hat.

Dann fand ich Desmonds Antwort und beschloss, seine magische Zahl als Ausgangspunkt zu versuchen. Da ich einen 6-Kern-Prozessor habe, habe ich ihn parallel ausgeführt, beginnend bei 0x07EDD5E59A4E28C2 / 6-Vielfachen. Ich war überrascht, dass es sofort etwas gefunden hat. Es stellt sich heraus, dass 0x07EDD5E59A4E28C2 / 2 funktioniert hat.

Hier ist also der Code für 0x07EDD5E59A4E28C2, der Ihnen eine Verschiebung und Subtraktion erspart:

int LogBase2(uint64_t n)
{
    static const int table[64] = {
        0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61,
        51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, 62,
        57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56,
        45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5, 63 };

    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n |= n >> 32;

    return table[(n * 0x03f6eaf2cd271461) >> 58];
}

Ganzzahliger Logarithmus zur Basis 2

Folgendes mache ich für 64-Bit-Ganzzahlen ohne Vorzeichen. Dies berechnet den Boden des Basis-2-Logarithmus, der dem Index des höchstwertigen Bits entspricht. Diese Methode ist rauchend schnell für große Zahlen, weil es eine ungerollte Schleife verwendet, die immer in log₂64 = 6 Schritten ausgeführt wird.

Im Wesentlichen subtrahiert es zunehmend kleinere Quadrate in der Folge { 0 ≤ k ≤ 5: 2^(2^k) } = { 2³², 2¹⁶, 2⁸, 2⁴, 2², 2¹ } = { 4294967296, 65536, 256 , 16, 4, 2, 1 } und summiert die Exponenten k der subtrahierten Werte.

int uint64_log2(uint64_t n)
{
  #define S(k) if (n >= (UINT64_C(1) << k)) { i += k; n >>= k; }

  int i = -(n == 0); S(32); S(16); S(8); S(4); S(2); S(1); return i;

  #undef S
}

Beachten Sie, dass dies –1 zurückgibt, wenn die ungültige Eingabe von 0 gegeben wird (was die anfängliche -(n == 0) sucht nach). Wenn Sie nie erwarten, es mit aufzurufen n == 0könnten Sie ersetzen int i = 0; für den Initialisierer und hinzufügen assert(n != 0); beim Einstieg in die Funktion.

Ganzzahliger Logarithmus zur Basis 10

Ganzzahlige Logarithmen zur Basis 10 können auf ähnliche Weise berechnet werden – wobei das größte zu testende Quadrat 10¹⁶ ist, weil log₁₀2⁶⁴ ≅ 19,2659… was von Natur aus langsam ist. Eine schnellere Implementierung wäre die Verwendung eines Akkumulators mit Werten, die exponentiell wachsen, und ein Vergleich mit dem Akkumulator, wodurch eine Art binäre Suche durchgeführt wird.)

int uint64_log10(uint64_t n)
{
  #define S(k, m) if (n >= UINT64_C(m)) { i += k; n /= UINT64_C(m); }

  int i = -(n == 0);
  S(16,10000000000000000); S(8,100000000); S(4,10000); S(2,100); S(1,10);
  return i;

  #undef S
}

Hier ist eine ziemlich kompakte und schnelle Verlängerung ohne zusätzliche Provisorien:

r = 0;

/* If its wider than 32 bits, then we already know that log >= 32.
So store it in R.  */
if (v >> 32)
  {
    r = 32;
    v >>= 32;
  }

/* Now do the exact same thing as the 32 bit algorithm,
except we ADD to R this time.  */
if (tt = v >> 16)
  {
    r += (t = tt >> 8) ? 24 + LogTable256
  }
else
  {
    r += (t = v >> 8) ? 8 + LogTable256
  }

Hier ist einer mit einer Kette von gebaut ifs, wieder ohne zusätzliche Provisorien. Ist aber vielleicht nicht der schnellste.

  if (tt = v >> 48)
    {
      r = (t = tt >> 8) ? 56 + LogTable256
    }
  else if (tt = v >> 32)
    {
      r = (t = tt >> 8) ? 40 + LogTable256
    }
  else if (tt = v >> 16)
    {
      r = (t = tt >> 8) ? 24 + LogTable256
    }
  else 
    {
      r = (t = v >> 8) ? 8 + LogTable256
    }

Wenn Sie nach der C++-Antwort gesucht haben und hierher gekommen sind, und da es darauf hinausläuft, Nullen zu zählen, dann haben Sie die std::countl_zero was laut godbolt.org anruft bsr.
std::countl_zero ab C++20 verfügbar ist, müssen Sie möglicherweise hinzufügen -std=gnu++2a zu Ihrer Compiler-Befehlszeile

Der Algorithmus findet grundsätzlich heraus, welches Byte das höchstwertige 1 Bit enthält, und sucht dann dieses Byte in der Suche nach dem Protokoll des Bytes und fügt es dann der Position des Bytes hinzu.

Hier ist eine etwas vereinfachte Version des 32-Bit-Algorithmus:

if (tt = v >> 16)
{
    if (t = tt >> 8)
    {
        r = 24 + LogTable256
    }
    else
    {
        r = 16 + LogTable256[tt];
    }
}
else 
{
    if (t = v >> 8)
    {
        r = 8 + LogTable256
    }
    else
    {
        r = LogTable256[v];
    }
}

Dies ist der entsprechende 64-Bit-Algorithmus:

if (ttt = v >> 32)
{
    if (tt = ttt >> 16)
    {
        if (t = tt >> 8)
        {
            r = 56 + LogTable256
        }
        else
        {
            r = 48 + LogTable256[tt];
        }
    }
    else 
    {
        if (t = ttt >> 8)
        {
            r = 40 + LogTable256
        }
        else
        {
            r = 32 + LogTable256[ttt];
        }
    }
}
else
{
    if (tt = v >> 16)
    {
        if (t = tt >> 8)
        {
            r = 24 + LogTable256
        }
        else
        {
            r = 16 + LogTable256[tt];
        }
    }
    else 
    {
        if (t = v >> 8)
        {
            r = 8 + LogTable256
        }
        else
        {
            r = LogTable256[v];
        }
    }
}

Ich habe einen Algorithmus für alle Größentypen entwickelt, der meiner Meinung nach schöner ist als das Original.

unsigned int v = 42;
unsigned int r = 0;
unsigned int b;
for (b = sizeof(v) << 2; b; b = b >> 1)
{
    if (v >> b)
    {
        v = v >> b;
        r += b;
    }
}

Notiz: b = sizeof(v) << 2 setzt b auf die Hälfte der Anzahl von Bits in v. Ich habe hier Verschiebung statt Multiplikation verwendet (nur weil ich Lust dazu hatte).

Sie könnten diesem Algorithmus eine Nachschlagetabelle hinzufügen, um ihn möglicherweise zu beschleunigen, aber es ist eher ein Proof-of-Concept.