Comment écrire la base de journal (2) en c / c ++

Existe-t-il un moyen d'écrire la fonction de journal (base 2)?

Le langage C a 2 fonctions intégrées - >>

1. logqui est la base e.

2. log10base 10;

Mais j'ai besoin de la fonction de journal de la base 2.Comment calculer cela.

Mathématiques simples:

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

où y peut être n'importe quoi, ce qui pour les fonctions de journal standard est soit 10, soit e .

C99 a log2(ainsi que log2fet log2lpour float et long double).

Si vous recherchez un résultat intégral, vous pouvez simplement déterminer le bit le plus élevé défini dans la valeur et renvoyer sa position.

#define M_LOG2E 1.44269504088896340736 // log2(e)

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

(la multiplication peut être plus rapide que la division)

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

Comme indiqué sur http://en.wikipedia.org/wiki/Logarithm :

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

Ce qui signifie que:

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

Si vous voulez le rendre rapide, vous pouvez utiliser une table de recherche comme dans Bit Twiddling Hacks (entiers log2 uniquement).

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];

De plus, vous devriez jeter un œil aux méthodes intégrées de vos compilateurs, comme celle _BitScanReversequi pourrait être plus rapide car elle peut être entièrement calculée en matériel.

Jetez également un œil aux doublons possibles Comment faire un entier log2 () en 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;
 }

Fondamentalement, le même que celui de tomlogic .

Vous devez inclure math.h (C) ou cmath (C ++) Bien sûr, gardez à l'esprit que vous devez suivre les mathématiques que nous connaissons ... seuls les nombres> 0.

Exemple:

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

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

J'avais besoin d'avoir plus de précision que la position du bit le plus significatif, et le microcontrôleur que j'utilisais n'avait pas de bibliothèque mathématique. J'ai trouvé que simplement utiliser une approximation linéaire entre 2 ^ n valeurs pour les arguments de valeur entière positive fonctionnait bien. Voici le 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));
}

Dans mon programme principal, j'avais besoin de calculer N * log2 (N) / 2 avec un résultat entier:

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

et toutes les valeurs 16 bits n'ont jamais été décalées de plus de 2%

Toutes les réponses ci-dessus sont correctes. Cette réponse ci-dessous peut être utile si quelqu'un en a besoin. J'ai vu cette exigence dans de nombreuses questions que nous résolvons en utilisant C.

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

Cependant, si vous utilisez le langage C et que vous voulez que le résultat soit un entier, vous pouvez utiliser ce qui suit:

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

J'espère que cela t'aides.

Consultez vos cours de mathématiques de base, log n / log 2. Peu importe que vous choisissiez logou log10dans ce cas, diviser par logla nouvelle base fait l'affaire.

Version améliorée de ce qu'a fait Ustaman Sangat

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

    return val;
}