Le calcul de l'étage de log_2(x) en utilisant seulement les opérateurs sur les bits en C

Votre résultat est tout simplement le rang de la plus grande non-null peu.

int log2_floor (int x)
{
    int res = -1;
    while (x) { res++ ; x = x >> 1; }
    return res;
}

Une solution possible est de prendre cette méthode:

Il est basé sur l'additivité des logarithmes:

log₂(2ⁿx) = log₂(x) + n

Laisser x₀ être un certain nombre de 2n bits (par exemple, n=16, 32 bits).

si x₀ > 2ⁿ, nous pouvons définir x₁ de sorte que
x₀ = 2ⁿx₁
et on peut dire que
E(log₂(x₀)) = n + E(log₂(x₁))

Nous pouvons calculer
x₁
avec un décalage binaires:
x₁ = x₀ >> n

Sinon, on peut simplement définir X₁ = X₀

Nous sommes maintenant confrontés au même problème avec le reste de la moitié supérieure ou inférieure de x₀

Par fractionnement de x dans la moitié à chaque étape, on peut calculer E(log₂(x)):

int log2_floor (unsigned x)
{
    #define MSB_HIGHER_THAN(n) (x &(~((1<<n)-1)))
    int res = 0;
    if MSB_HIGHER_THAN(16) {res+= 16; $x >>= 16;}
    if MSB_HIGHER_THAN( 8) {res+=  8; $x >>=  8;}
    if MSB_HIGHER_THAN( 4) {res+=  4; $x >>=  4;}
    if MSB_HIGHER_THAN( 2) {res+=  2; $x >>=  2;}
    if MSB_HIGHER_THAN( 1) {res+=  1;}
    return res;
}

Depuis votre sadique professeur a dit que vous ne pouvez pas utiliser de boucles, nous pouvons pirater notre façon de contourner par le calcul d'une valeur qui sera n en cas de test positif et 0 dans le cas contraire, n'a donc aucun effet sur plus ou maj:

#define N_IF_MSB_HIGHER_THAN_N_OR_ELSE_0(n) (((-(x>>n))>>n)&n)

Si le - opérateur est également interdite par vos troubles psychopathiques de l'enseignant (ce qui est stupide car les processeurs sont capables de gérer les 2 complète aussi bien que des opérations bit à bit), vous pouvez utiliser -x = ~x+1 dans la formule ci-dessus

#define N_IF_MSB_HIGHER_THAN_N_OR_ELSE_0_WITH_NO_MINUS(n) (((~(x>>n)+1)>>n)&n)

qui nous permettra de réduire de NIMHTNOE0WNM pour des raisons de lisibilité.

Aussi, nous allons utiliser | au lieu de + puisque nous savons qu'il sera pas de report.

Ici l'exemple est de 32 bits entiers, mais vous pouvez le faire fonctionner sur 64, 128, 256, 512 ou 1024 bits entiers si vous avez réussi à trouver un langage qui prend en charge un nombre entier.

int log2_floor (unsigned x)
{
    #define NIMHTNOE0WNM(n) (((~(x>>n)+1)>>n)&n)

    int res, n;

    n = NIMHTNOE0WNM(16); res  = n; x >>= n;
    n = NIMHTNOE0WNM( 8); res |= n; x >>= n;
    n = NIMHTNOE0WNM( 4); res |= n; x >>= n;
    n = NIMHTNOE0WNM( 2); res |= n; x >>= n;
    n = NIMHTNOE0WNM( 1); res |= n;
    return res;
}

Ah, mais peut-être qu'il vous était interdit d'utiliser #define trop?
Dans ce cas, je ne peux pas faire beaucoup plus pour vous, sauf vous conseillons de le revendre à votre enseignant de la mort avec une vieille édition du K&R.

Cela conduit à inutiles, d'obfuscation de code qui dégage une forte odeur de non lavés 70 hackers.

La plupart, si pas tous les processeurs en œuvre des "compter les zéros à gauche" instructions (par exemple, clz sur les BRAS, bsr sur x86 ou cntlz sur PowerPC) qui peut faire l'affaire sans tout ce tapage .

OriginalL'auteur

La question est égal à "trouver le bit le plus élevé de 1 du nombre binaire"

ÉTAPE 1: définir la gauche de 1 tous 1
comme 0x07000000 à 0x07ffffff

x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16); //number of ops = 10

ÉTAPE 2: renvoie le nombre de 1 dans word et moins 1

Référence: Le poids de Hamming

//use bitCount
int m1 = 0x55; //01010101...
m1 = (m1 << 8) + 0x55;
m1 = (m1 << 8) + 0x55;
m1 = (m1 << 8) + 0x55;
int m2 = 0x33; //00110011...
m2 = (m2 << 8) + 0x33;
m2 = (m2 << 8) + 0x33;
m2 = (m2 << 8) + 0x33;
int m3 = 0x0f; //00001111...
m3 = (m3 << 8) + 0x0f;
m3 = (m3 << 8) + 0x0f;
m3 = (m3 << 8) + 0x0f;
x = x + (~((x>>1) & m1) + 1); //x - ((x>>1) & m1)
x = (x & m2) + ((x >> 2) & m2);
x = (x + (x >> 4)) & m3;
//x = (x & m3) + ((x >> 4) & m3);
x += x>>8;
x += x>>16;
int bitCount =  x & 0x3f; //max 100,000(2) = 32(10)
//Number of ops: 35 + 10 = 45
return bitCount + ~0;

C'est comment je le fais. Merci~

OriginalL'auteur mi al

J'ai aussi été affecté à ce problème pour les devoirs et j'ai passé une quantité importante de temps à réfléchir à ce sujet donc je pensais que je voudrais partager ce que je suis venu avec. Cela fonctionne avec des entiers sur un ordinateur 32 bits. !!x retourne si x est zéro ou un.

int ilog2(int x) {
int byte_count = 0;
int y = 0;
//Shift right 8
y = x>>0x8;
byte_count += ((!!y)<<3);
//Shift right 16
y = x>>0x10;
byte_count += ((!!y)<<3);
//Shift right 24 and mask to adjust for arithmetic shift
y = (x>>0x18)&0xff;
byte_count += ((!!y)<<3);
x = (x>>byte_count) & 0xff;
x = x>>1;
byte_count += !!x;
x = x>>1;
byte_count += !!x;
x = x>>1;
byte_count += !!x;
x = x>>1;
byte_count += !!x;
x = x>>1;
byte_count += !!x;
x = x>>1;
byte_count += !!x;
x = x>>1;
byte_count += !!x;
x = x>>1;            //8
byte_count += !!x;
return byte_count;
}

OriginalL'auteur swsmith