Question Comment trouver un logarithme binaire très rapide? (O (1) au mieux)


Existe-t-il une méthode très rapide pour trouver un logarithme binaire d'un nombre entier? Par exemple, donner un numéro x = 52656145834278593348959013841835216159447547700274555627155488768 un tel algorithme doit trouver y = log (x, 2) qui est 215. x est toujours une puissance de 2.

Le problème semble être très simple. Il suffit de trouver la position du 1 bit le plus significatif. Il existe une méthode bien connue, FloorLog, mais elle n'est pas très rapide, surtout pour les très longs entiers multi-mots.

Quelle est la méthode la plus rapide?


13
2018-04-19 14:34


origine


Réponses:


Est Bit Twiddling Hacks Qu'est-ce que vous cherchez?


21
2018-04-19 14:42



Un hack rapide: La plupart des représentations numériques à virgule flottante normalisent automatiquement les valeurs, ce qui signifie qu'elles effectuent efficacement la boucle. Christoffer Hammarström mentionné en matériel. Donc, convertir simplement un entier en FP et extraire l'exposant devrait faire l'affaire, à condition que les nombres soient dans la plage d'exposant de la représentation FP! (Dans votre cas, votre saisie de nombres entiers nécessite plusieurs mots de machine, de sorte que plusieurs "décalages" devront être effectués lors de la conversion.)


6
2018-04-21 07:22



Si les entiers sont stockés dans un uint32_t a[], alors ma solution évidente serait la suivante:

  1. Lancer une recherche linéaire sur a[] trouver la valeur non nulle la plus élevée uint32_t valeur a[i] dans a[] (test en utilisant uint64_t pour cette recherche si votre machine est native uint64_t soutien)

  2. Appliquer le bidouilles trouver le journal binaire b du uint32_t valeur a[i] vous avez trouvé à l'étape 1.

  3. Évaluer 32*i+b.


4
2018-04-19 14:49



La réponse est l'implémentation ou la langue dépendante. Toute implémentation peut stocker le nombre de bits significatifs avec les données, car cela est souvent utile. S'il doit être calculé, trouvez le mot / membre le plus significatif et le bit le plus significatif dans ce mot.


2
2018-04-20 04:23



La meilleure option sur ma tête serait une approche O (log (logn)), en utilisant la recherche binaire. Voici un exemple pour un 64 bits ( <= 2^63 - 1 ) nombre (en C ++):

int log2(int64_t num) {
    int res = 0, pw = 0;    
    for(int i = 32; i > 0; i --) {
        res += i;
        if(((1LL << res) - 1) & num)
            res -= i;
    }
    return res;
}

Cet algorithme va essentiellement me proférer avec le plus grand nombre de res tel que (2^res - 1 & num) == 0. Bien sûr, pour n'importe quel nombre, vous pouvez travailler sur un sujet similaire:

int log2_better(int64_t num) {
    var res = 0;
    for(i = 32; i > 0; i >>= 1) {
        if( (1LL << (res + i)) <= num )
            res += i;
    }
    return res;
}

Notez que cette méthode repose sur le fait que l'opération "bitshift" est plus ou moins O (1). Si ce n'est pas le cas, vous devrez pré-calculer soit toutes les puissances de 2, soit les nombres de forme 2^2^i (2 ^ 1, 2 ^ 2, 2 ^ 4, 2 ^ 8, etc.) et faites des multiplications (qui dans ce cas ne sont plus O (1)).


0
2018-06-23 07:08



Vous pouvez créer un tableau de logarithmes au préalable. Cela trouvera des valeurs logarithmiques allant jusqu'à log (N):

#define N 100000
int naj[N];

naj[2] = 1;
for ( int i = 3; i <= N; i++ )
{
    naj[i] = naj[i-1];
    if ( (1 << (naj[i]+1)) <= i )
        naj[i]++;

}

Le tableau naj correspond à vos valeurs logarithmiques. Où naj [k] = log (k). Le journal est basé sur deux.


0
2017-10-21 21:55