So schreiben Sie die Protokollbasis (2) in c / c ++

Gibt es eine Möglichkeit, die Protokollfunktion (Basis 2) zu schreiben?

Die C-Sprache hat 2 eingebaute Funktionen - >>

1. logwelches ist Basis e.

2. log10Basis 10;

Aber ich brauche die Log-Funktion von Basis 2.Wie man das berechnet.

Einfache Mathematik:

    log ₂ ( x ) = log _y ( x ) / log _y (2)

Dabei kann y alles sein, was für Standardprotokollfunktionen entweder 10 oder e ist .

C99 hat log2(sowie log2fund log2lfür Float und Long Double).

Wenn Sie nach einem ganzzahligen Ergebnis suchen, können Sie einfach das höchste im Wert gesetzte Bit bestimmen und seine Position zurückgeben.

#define M_LOG2E 1.44269504088896340736 // log2(e)

inline long double log2(const long double x){
    return log(x) * M_LOG2E;
}

(Multiplikation kann schneller sein als Division)

log2(int n) = 31 - __builtin_clz(n)

Wie auf http://en.wikipedia.org/wiki/Logarithm angegeben :

logb(x) = logk(x) / logk(b)

Was bedeutet, dass:

log2(x) = log10(x) / log10(2)

Wenn Sie es schnell machen möchten, können Sie eine Nachschlagetabelle wie in Bit Twiddling Hacks verwenden (nur Ganzzahl log2).

uint32_t v; // find the log base 2 of 32-bit v
int r;      // result goes here

static const int MultiplyDeBruijnBitPosition[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
};

v |= v >> 1; // first round down to one less than a power of 2 
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];

Darüber hinaus sollten Sie einen Blick auf Ihren Compiler builtin Methoden nehmen wie _BitScanReversedie könnten schneller sein , weil es vollständig in Hardware berechnet werden.

Schauen Sie sich auch mögliche Duplikate an. Wie erstelle ich eine Ganzzahl log2 () in C ++?

log2(x) = log10(x) / log10(2)

uint16_t log2(uint32_t n) {//but truncated
     if (n==0) throw ...
     uint16_t logValue = -1;
     while (n) {//
         logValue++;
         n >>= 1;
     }
     return logValue;
 }

Grundsätzlich das gleiche wie bei Tomlogic .

Sie müssen math.h (C) oder cmath (C ++) einschließen. Denken Sie natürlich daran, dass Sie die Mathematik befolgen müssen, die wir kennen ... nur Zahlen> 0.

Beispiel:

#include <iostream>
#include <cmath>
using namespace std;

int main(){
    cout<<log2(number);
}

Ich musste präziser sein als nur die Position des höchstwertigen Bits, und der von mir verwendete Mikrocontroller hatte keine Mathematikbibliothek. Ich fand heraus, dass nur die Verwendung einer linearen Näherung zwischen 2 ^ n-Werten für positive Ganzzahlwertargumente gut funktioniert. Hier ist der Code:

uint16_t approx_log_base_2_N_times_256(uint16_t n)
{
    uint16_t msb_only = 0x8000;
    uint16_t exp = 15;

    if (n == 0)
        return (-1);
    while ((n & msb_only) == 0) {
        msb_only >>= 1;
        exp--;
    }

    return (((uint16_t)((((uint32_t) (n ^ msb_only)) << 8) / msb_only)) | (exp << 8));
}

In meinem Hauptprogramm musste ich N * log2 (N) / 2 mit einem ganzzahligen Ergebnis berechnen:

temp = (((uint32_t) N) * approx_log_base_2_N_times_256) / 512;

und alle 16-Bit-Werte waren nie um mehr als 2% niedriger

Alle obigen Antworten sind richtig. Diese Antwort von mir unten kann hilfreich sein, wenn jemand sie braucht. Ich habe diese Anforderung in vielen Fragen gesehen, die wir mit C lösen.

log2 (x) = logy (x) / logy (2)

Wenn Sie jedoch die Sprache C verwenden und das Ergebnis in einer Ganzzahl anzeigen möchten, können Sie Folgendes verwenden:

int result = (int)(floor(log(x) / log(2))) + 1;

Hoffe das hilft.

Konsultieren Sie Ihren Grundkurs Mathematik log n / log 2. Es spielt keine Rolle, ob Sie wählen logoder log10in diesem Fall ist das Teilen durch logdie neue Basis der Trick.

Verbesserte Version von Ustaman Sangat

static inline uint64_t
log2(uint64_t n)
{
    uint64_t val;
    for (val = 0; n > 1; val++, n >>= 1);

    return val;
}