La décision frontale est de faire une boucle et dans cette boucle, divisez constamment le nombre par deux jusqu'à ce qu'il devienne zéro. Combien de telles divisions se sont produites, telle est la valeur du logarithme. Oui, cette méthode fonctionne et a droit à la vie, mais je veux montrer comment cela peut être fait sans cycles et structures complexes.
Donc, nous voulons calculer la formule suivante:
Décision
Pour ceux qui ne sont pas intéressés par le raisonnement, je vais immédiatement donner des fonctions prêtes à l'emploi pour calculer le logarithme:
uint32_t getHighBit_32(uint32_t x)
{
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x - (x >> 1);
}
uint32_t getBitCount_32(uint32_t x)
{
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
return (x & 0x0000FFFF) + (x >> 16);
}
uint32_t getLog2_32(uint32_t x)
{
return getBitCount_32(getHighBit_32(x) - 1);
}
Explications
Commençons par convertir le nombre x en une notation binaire d'une certaine longueur.
Par exemple, length = 8, mais cela n'a pas d'importance et la longueur du nombre peut être quelconque.
Rappelez-vous maintenant sur quoi est basée la traduction d'un nombre en notation binaire. Représenter le nombre comme une somme de puissances de deux. Le nombre de degrés déterminera la position du bit, qui est 1. Par exemple:... Ceux. nombres de puissance 5, 3, 2 et 0. Cela signifie que les 5ème, 3ème, 2ème, 0ème bits sont égaux à 1. Le reste des bits entre eux est égal à zéro. Les bits commencent par le côté droit. Il s'est avéré que
On peut noter que la traduction en notation binaire est étroitement liée à l'exponentiation, et le logarithme est l'inverse de l'exponentiation et est égal à l'exposant.
De plus, l'exposant auquel 2 doit être élevé est le nombre d'un seul bit dans une notation binaire. Il s'avère que si vous trouvez le nombre d'un seul bit, alors nous obtenons la partie entière de la valeur du logarithme en base deux. Par exemple, si 32 = 100000, le bit est à la 5ème place, donc le logarithme est 5.
Mais comme il peut y en avoir plusieurs, pas 1, la question se pose de savoir quel bit prendre pour trouver le logarithme. La réponse est le numéro du dernier bit, en partant du côté droit du nombre, car c'est la puissance la plus élevée de deux qui détermine toute la partie du logarithme, le reste constitue la partie fractionnaire du logarithme.
Prenons un autre exemple - un nombre... Le dernier bit est à la 5ème place, donc la partie entière du logarithme de 45 est 5. et en effet... Nous rejetons la partie fractionnaire et laissons 5.
Cela fonctionne également avec d'autres nombres.
En conséquence, nous avons obtenu que la partie entière du logarithme est égale au nombre du dernier bit, en partant de la droite. Question: comment trouver le numéro du dernier bit?
Pour cela, il existe des fonctions basées sur des opérations au niveau du bit, que j'ai trouvées dans le livre de G. Warren "Algorithmic tricks for programmers".
- Arrondir à une puissance de deux (ou mettre en évidence le dernier bit dans la notation binaire d'un nombre). En fait, vous pouvez arrondir, mais la valeur du logarithme sera également arrondie.
- Compter le nombre de bits simples dans la notation binaire d'un nombre
Les deux fonctions y sont bien décrites, et j'ai donné leur code plus tôt.
En utilisant ces deux fonctions, l'algorithme de calcul de l'algorithme est le suivant:
- Sélectionnez le dernier bit du numéro. Maintenant, le nombre s'écrit 100000
- Soustrayez un du nombre résultant. Ensuite, le numéro sera comme ceci: 011111
- Comptez le nombre de bits d'unité et ce sera la valeur entière du logarithme
Situation exceptionnelle
Le logarithme a une situation exceptionnelle lorsque x = 0. En théorie, un tel algorithme n'existe pas (ou dans la limite il est égal à -∞). Cependant, comme on s'écarte un peu des lois des mathématiques en programmation, les fonctions fonctionnent toujours même lorsque l'entrée de la fonction est nulle. Dans ce cas, la valeur du logarithme sera 32 (si le nombre est 32 bits). En effet, la fonction d'arrondi à la puissance de deux la plus proche donnera 0, puis nous soustrayons un de zéro et obtenons le nombre 0xFFFFFFFF, et il y a 32 unités dans ce nombre, donc le logarithme sera 32.
Oui, du point de vue des mathématiques, c'est incorrect, mais il y a des cas, quand c'est utile du point de vue de la programmation.
Compter la longueur d'un code binaire
Il est peu probable qu'une telle fonction soit utilisée pour calculer le logarithme mathématique, car les logarithmes sont plus souvent considérés à partir de nombres réels et non d'entiers.
Cependant, le calcul de la longueur d'un code binaire est une tâche plus courante dans la pratique.
Soit un code binaire d'une certaine longueur. Cela peut être, par exemple, un chemin dans un arbre binaire. Si un seul bit est écrit devant ce code, alors il est possible de calculer la longueur de ce code sans utiliser de variables auxiliaires en prenant un logarithme entier.
Par exemple, donnons le code 0001110110. Il est écrit, par exemple, dans une cellule de 32 bits et nous avons souvent besoin de lire la longueur de ce code. Pour ce faire, ajoutez un bit supplémentaire avant le code.
Nous obtenons: 10001110110. Et maintenant, nous pouvons calculer en toute sécurité la longueur de ce code à travers le logarithme entier, sans stocker séparément la longueur de ce code ailleurs.
Si nous considérons la longueur du code, où tous sont des zéros, alors la fonction retournera la longueur = 32, ce qui peut être incorrect, donc cette situation doit être prévue. Dans certaines situations, il est utile que la fonction renvoie 32 et dans d'autres, par exemple, zéro.
Sources
- G. Warren «Trucs algorithmiques pour les programmeurs. Édition révisée. ", 2004