Gibt es eine Möglichkeit, die Protokollfunktion (Basis 2) zu schreiben?
Die C-Sprache hat 2 eingebaute Funktionen - >>
1. log
welches ist Basis e.
2. log10
Basis 10;
Aber ich brauche die Log-Funktion von Basis 2.Wie man das berechnet.
Gibt es eine Möglichkeit, die Protokollfunktion (Basis 2) zu schreiben?
Die C-Sprache hat 2 eingebaute Funktionen - >>
1. log
welches ist Basis e.
2. log10
Basis 10;
Aber ich brauche die Log-Funktion von Basis 2.Wie man das berechnet.
Einfache Mathematik:
log 2 ( x ) = log y ( x ) / log y (2)
Dabei kann y alles sein, was für Standardprotokollfunktionen entweder 10 oder e ist .
Wenn Sie nach einem ganzzahligen Ergebnis suchen, können Sie einfach das höchste im Wert gesetzte Bit bestimmen und seine Position zurückgeben.
Integer.highestOneBit(int)
Methode):i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); return i - (i >>> 1);
while (i >>= 1) { ++l; }
i>>32
. Da Java jedoch nur 32-Bit-Ints hat, ist dies in Ordnung. Für C / C ++ muss dies berücksichtigt werden.
#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)
log()
Implementierung nie sieht , wird er dies nicht tun. Mein Fehler.
log10()
eine Funktion im C-Standard definiert ist, kann der Compiler sie "speziell" behandeln, einschließlich der Vorberechnung des Ergebnisses, was meiner Meinung nach @Johannes 'Vorschlag war?
log10(2)
durch eine Konstante ersetzt.
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 _BitScanReverse
die 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 log
oder log10
in diesem Fall ist das Teilen durch log
die 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;
}