Le moyen le plus rapide de trouver une base binaire

Question

J'essaie de trouver la base binaire d'un nombre, comme la fonction floor qui arrondit un nombre au plus grand entier inférieur, Je veux arrondir le nombre à la 1ère base binaire inférieure.

Par exemple :

for 1000 it should be 512
for 10 it should be 8
for 208 it should be 128

C'est ce que j'ai essayé. Je sens les fonctions de log consomment plus de ressources alors y a-t-il un approche plus rapide pour ça ?

#include<stdio.h>
int main()  {
    unsigned long long int num;
    unsigned long long int mask;
    scanf("%llu", &num);
    mask = 0x80000000;
    while(mask >>= 1)   {
        if (mask & num)
            break;
    }
    printf("%llu\n", mask);
    return 0;
}

Merci :)

Answer 1

int topBit(int n) {
    while (true){
        m = n & (n-1);
        if (m == 0) return n;
        n = m;
    } 
}

n & (n-1) efface le bit le plus bas. Faites cela jusqu'à ce que vous atteigniez zéro, et vous saurez alors que la valeur précédente n'avait qu'un seul bit activé (le plus haut qui était activé dans l'entrée).

Answer 2

Représentez le nombre en binaire, puis recherchez le bit le plus significatif (le bit non nul le plus élevé). Naïvement, vous pouvez le faire en décalant vers la droite un bit à la fois jusqu'à ce qu'il soit nul - c'était "un de trop". C'est en gros l'approche que vous avez essayée. Une recherche binaire serait un peu plus rapide. Pour un entier de 32 bits, décalez vers la droite de 16 ; si c'est toujours > 0, décalez vers la droite de 8, etc. Je suis sûr que vous pouvez trouver la solution à partir de là.

Exemple de code :

typedef unsigned long long int ulli;
ulli floor2(ulli num){
  int msb = 8*sizeof(num)/2;
  ulli temp = ((ulli)1)<<msb;
  while(msb>1){
    msb/=2; // using divide for clarity
    if(temp>num) temp>>=msb; else temp<<=msb;
  }
  if (temp>num) temp/=2;
  return temp;
}

J'ai effectué quelques tests de cet algorithme par rapport à l'algorithme de la topBit ainsi que le builtIn méthode. Une boucle avec 10M itérations, générant un nombre aléatoire "long", prend 362 ms sur mon système (sans optimisation du compilateur). Si la boucle inclut l'une des méthodes de calcul, les temps augmentent comme suit :

=============  total    net
builtin:         407     45
binary search:   579    215
topBit:         2295   1933

La méthode intégrée est certainement la plus rapide, et de loin, ce qui n'est pas vraiment surprenant ! Avec des nombres de 64 bits, topBit aura besoin en moyenne de 32 boucles (la moitié des bits étant activés, ils sont ignorés) et la méthode binaire de seulement 5 boucles, ce qui laisse espérer une différence de vitesse de 6x ; c'est à peu près ce que vous voyez. Lorsque je définis ulli como unsigned short (16 bits), la différence de temps est d'environ 2x.

Answer 3

Vous pouvez le faire en utilisant GCC builtins si vous compilez avec GCC. La fonction intégrée __builtin_clzll compte le nombre de zéros de tête dans une longue non signée. Vous pouvez l'utiliser pour calculer la position du bit le plus significatif, puis décaler 1 à gauche autant de fois pour obtenir votre réponse :

#include <limits.h>

Alors utilisez :

unsigned long long result = 
  num ? 1LLU << (sizeof(unsigned long long)*CHAR_BIT - __builtin_clzll(num) - 1) : 0;

printf("%llu\n", result);

Answer 4

Ce document classique a de nombreuses façons de trouver le plancher (log base 2) d'un nombre entier. Après avoir trouvé le log, le nombre que vous voulez est bien sûr 1 << log.

La suggestion la plus fascinante est la suivante

// Find the integer log base 2 of an integer with an 64-bit IEEE float 
int v; // 32-bit integer to find the log base 2 of
int r; // result of log_2(v) goes here
union { unsigned int u[2]; double d; } t; // temp

t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = v;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;

Le code ci-dessus charge un double de 64 bits (IEEE-754 à virgule flottante) avec un entier de 32 bits (sans bits de remplissage) en stockant l'entier dans la mantisse tandis que l'exposant est fixé à 252. De ce nouveau double, 252 (exprimé en double) est soustrait, ce qui fixe l'exposant résultant au logarithme de base 2 de la valeur d'entrée, v. Il ne reste plus qu'à décaler les bits de l'exposant en position (20 bits à droite) et à soustraire le biais, 0x3FF (qui est 1023 en décimal). Cette technique ne nécessite que 5 opérations, mais de nombreux processeurs sont lents à manipuler les doubles, et il faut tenir compte du caractère endien de l'architecture.

Donc le résultat final que vous voulez sera 1 << r . Notez que la manipulation des doubles est beaucoup plus rapidement maintenant que lorsque cet article a été écrit. La meilleure chose à propos de ce code est qu'il ne contient pas de branches, et qu'il est donc bien structuré. Vous devriez vraiment l'essayer. Je n'ai pas le temps d'essayer un benchmark pour le moment, mais ce serait intéressant.

Je ne peux pas garantir que ce code répond à la norme C.

Answer 5

Je suppose que si un nombre est déjà une puissance de 2 ou zéro, il devrait être renvoyé sans changement. Uniquement les nombres positifs.

int floor2(int n)
{
    if ((n & (n-1)) == 0)
        return n;
    while (((n+1) & n) != 0)
    {
        n = n | (n+1);
    }
    return (n + 1) >> 1;
}

La manipulation des bits de fantaisie tire parti du fait que la soustraction de 1 à un nombre à un seul bit (c'est-à-dire une puissance de 2) active tous les bits inférieurs, tandis que l'ajout de 1 à un nombre active le bit zéro le plus bas.