algorithme simple de la difficulté à comprendre

Question

désolé pour cette question spécifique, mais à regarder l'algorithme suivant écrit en Javascript

function c(a) { 
    if (a < 2) return 2; 
    if (a > 4096) return 4096; 
    var b = a & (a - 1); 
    while (b > 0) { 
     a++; 
     b = a & (a - 1) 
    } 
    return a 
} 

Je suis tombé sur une déclaration que je n'étais pas sûr. Que fait exactement ? J'étais sous l'hypothèse qu'il assignait A à B et soustrait 1 de B, cependant, si c'était le cas, alors B n'atteindrait jamais 0 (ou en dessous de 0) résultant en une boucle infinie? Comment cela peut-il fonctionner?

Je pose cette question parce que j'ai essayé d'adapter l'algorithme à PHP, mais j'ai frappé un mur. Cela fonctionne parfaitement en Javascript, donc je sais avec certitude que je ne comprends pas ce qui se passe. Voici ma tentative en PHP:

function c($a) { 
    if ($a < 2) return 2; 
    if ($a > 4096) return 4096; 
     $b = $a 
     $b = ($b - 1); 
    while ($b > 0) { 
     $a++; 
     $b = $a; 
     $b -= 1; 
    } 
    return $b; 
} 

Je vois bien pourquoi il ne fonctionne pas, mais je ne suis pas sûr de savoir comment changer l'algorithme pour le faire fonctionner. Plus ou moins, je sais que je n'adapte pas l'algorithme correctement car je ne comprends pas comment cela fonctionne en Javascript.

De toute façon, s'il vous plaît aidez-moi! Je ne veux pas spécifiquement quelqu'un pour résoudre mon problème pour moi, mais un indice dans la bonne direction serait vraiment génial. . :(

Merci beaucoup

Answer 1

Cette ligne efface le bit de jeu le plus bas la valeur de a et affecte le résultat à b

Exemple:

00010100110101111000 

Devient:

00010100110101110000 
       ^

La raison pour laquelle cela fonctionne est que la soustraction d'un flips tous les bits jusqu'au bit le moins significatif qui a été défini. Tous les autres bits restent inchangés. En utilisant bitwise-et conserve tous les bits qui n'ont pas changé.

00010100110101111000 a 
00010100110101110111 a-1 
00010100110101110000 a & (a-1) 

---

Cette boucle ajoute de façon répétée un à a jusqu'à ce que la compensation d'un bit de a donne zéro:

b = a & (a - 1); 
while (b > 0) { 
    a++; 
    b = a & (a - 1); 
} 

En d'autres termes, il arrondit a à la puissance de 2 dans un très proche manière inefficace!

connexes

• Bit Twiddling Hacks - Round up to the next highest power of 2
• What are bitwise shift (bit-shift) operators and how do they work?

Answer 2

Thats une opération au niveau du bit:

http://en.wikipedia.org/wiki/Bitwise_operation

http://php.net/manual/en/language.operators.bitwise.php

Answer 3

Il est le même.

function c($a) { 
    if ($a < 2) return 2; 
    if ($a > 4096) return 4096; 
    $b = $a & ($a - 1); 
    while ($b > 0) { 
     $a++; 
     $b = $a & ($a - 1); 
    } 
    return $b; 
} 

Answer 4

Je pense qu'il retourne puissance de 2. Pour le plus proche suivant une puissance de 2 un & (a-1) renvoie 0.

Edit:

Je viens de vérifier cela en Java. Il fait revenir la puissance suivante 2. Lorsqu'un 6 est, elle retourne 8. Lorsqu'un 9 est elle retourne 16. Si un est 2 retourne 2.

Answer 5

a & (a-1) 

fera Bitwise et d'un et (un-1)

en php

$b = $a & ($a-1) 

devrait fonctionner aussi.

Answer 6

a & (a-1); 

Cette déclaration fait bit à bit ET entre a et a-1. This lien vous expliquer à propos des opérations Bit-wise. En PHP, vous pouvez utiliser l'opérateur & pour l'opération AND. Here est le lien lié à PHP.