Explication détaillée de la structure des données javascript et de l'algorithme

Veuillez implémenter une fonction qui saisit un entier et génère le nombre de 1 représenté par la représentation binaire du nombre. Par exemple, si 9 est représenté par 1001 en binaire, 2 bits valent 1. Donc, si vous entrez 9, la fonction génère 2. Tout d’abord, pour la solution du binaire 1, nous devrions surtout penser à quelques opérateurs sur les opérations sur les bits. Il existe cinq opérations au total, à savoir : AND (&), OR (|), XOR (^), décalage vers la droite (>>) et décalage vers la gauche (<<).

La première solution qui peut provoquer une boucle infinie :
Idée 1 : Jugez d'abord de l'entier que vous avez donné, si la partie la plus à droite de ce nombre est 1. Si c'est 1, donnez un compteur et ajoutez-y 1. Décalez ensuite l'entier d'entrée d'un bit vers la droite et continuez à décaler jusqu'à ce que l'entier devienne 0, puis sortez le compteur.

function NumberOf1(n)
{
  let count = 0;
  while(n) {
    if(n & 1) {
      count ++;
    }
    n = n >> 1;
  }
  return count;
}
console.log(NumberOf1(9));</p>
<p>Cet algorithme n'a aucun problème pour les nombres non signés, mais c'est un gros problème pour les nombres signés, et il est très susceptible de provoquer une boucle infinie. Lorsque n est un nombre négatif, n est décalé vers la droite et 1 est ajouté au bit le plus élevé (pour garantir que les données sont négatives), de sorte qu'une boucle infinie finira par se former. Par exemple : 0x80000000, un problème se produira à ce moment-là. Lorsqu'il est décalé d'une position vers la droite, il devient 0xC0000000. Puisqu'il s'agit d'un décalage d'un nombre négatif, il faut s'assurer que le nombre décalé est un nombre négatif, donc le bit le plus élevé sera toujours 1, ce qui signifie qu'à la fin ce nombre bouclera toujours sans fin. </p>
<p> Idée 2 : Déplacez 1, déterminez d'abord si le bit le plus bas est 1, puis déplacez 1 vers 2. Comparez-le ensuite avec le rapport entier pour déterminer si l'avant-dernier chiffre est 1, et ainsi de suite. . . De cette façon, un effet peut être obtenu au final et le nombre composé uniquement de 1 peut être obtenu. </p>
<pre class="brush:php;toolbar:false">function NumberOf1(n) {

  let count = 0;
  let flag = 1;
  while(flag) {
    if(n & flag) {
      count ++;
    }
    flag = flag << 1;
  }
  return count;
}
console.log(NumberOf1(9));

Enfin, nous proposons la meilleure méthode.

Idée 3 : soustrayez 1 d'un entier, puis effectuez une opération ET avec l'entier d'origine. Le 1 à l'extrême droite de l'entier sera transformé en 0, et tous les 0 après le 1 seront. transformé en 1. Ensuite, autant de 1 qu'il y a dans le système binaire d'un entier, cette opération peut être effectuée autant de fois que possible. Enfin, il suffit de déterminer le nombre d'opérations en utilisant le compteur et de sortir le compteur.

//更好的解法
function NumberOf1(n) {
  let count = 0;
  while(n) {
    count ++;
    n = (n-1) & n;
  }
  return count;
}
console.log(NumberOf1(9));

Recommandations associées :

Structure des données en PHP : Explication détaillée de l'extension DS

L'ordre de php structure de données Exemples de listes chaînées et de listes linéaires liées

Partage d'exemples de listes chaînées simples et de listes chaînées circulaires dans des structures de données JavaScript

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!