Quel est le moyen le plus efficace pour trouver le nombre de zéros de début et de fin d'un entier 32 bits non signé en Javascript

Question

Ma question est simplement: Quelle est la manière la plus efficace de trouver à la fois le nombre de zéros en tête (zéros avant le bit de premier set) et le nombre de zéros de fin (zéros après le dernier bit mis) dans un entier non signé de 32 bits?

Jusqu'ici, j'ai trouvé la solution this, mais je me demandais si quelqu'un connaissait des solutions plus rapides. Je sais aussi qu'il y a an efficient way de le faire en C++.

Answer 1

Après avoir fait quelques recherches, j'ai trouvé la solution this C, que je transposent alors Javascript comme ceci:

code en C (retourne la position de la droite du bit le plus significatif):

static const char LogTable256[256] = 
{ 
#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n 
    -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 
    LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6), 
    LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7) 
}; 

unsigned int v; // 32-bit word to find the log of 
unsigned r;  // r will be lg(v) 
register unsigned int t, tt; // temporaries 

if (tt = v >> 16) 
{ 
    r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt]; 
} 
else 
{ 
    r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v]; 
} 

code en Javascript (retourne le nombre de zéros en tête):

//http://graphics.stanford.edu/~seander/bithacks.html 
//Translated from C 
var logTable256 = [-1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 
        4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 
        5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
        6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
        6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7]; 
Number.prototype.leadingZeros = function() { 
    var r, t, tt; 
    if (tt = this >>> 16) { 
     r = (t = tt >>> 8) ? 24 + logTable256[t] : 15 - logTable256[tt]; 
    } 
    else { 
     r = (t = this >>> 8) ? 8 + logTable256[t] : 31 - logTable256[this]; 
    } 
    return r; 
} 

Ceci est environ deux fois plus vite que la méthode dans la question initiale .