Méditations LeetCode : Nombre de ses

Commençons par la description de celui-ci :

Étant donné un entier positif n, écrivez une fonction qui renvoie le nombre de bits définis dans sa représentation binaire (également connue sous le nom de poids de Hamming).

Par exemple :

Input: n = 11
Output: 3

Explanation: The input binary string 1011 has a total of three set bits.

Ou :

Input: n = 128
Output: 1

Explanation: The input binary string 10000000 has a total of one set bit.

Ou :

Input: n = 2147483645
Output: 30

Explanation: The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

---

Comme nous l'avons mentionné dans l'introduction du chapitre dans le post précédent, un set bit fait référence à un bit ayant la valeur 1.

Donc, ce que nous devons faire, c'est compter 1 bits.

Une façon de procéder consiste à convertir le nombre en chaîne et à compter simplement les 1. Ou bien, nous pouvons convertir cela en tableau, filtrer les 0 et obtenir sa longueur. Mais il existe une autre approche où nous pouvons utiliser la manipulation de bits.

Nous pouvons supprimer les bits définis (bits qui ont la valeur 1) jusqu'à ce que le nombre devienne 0.

Une bonne chose à savoir est que n - 1 est la version supprimée la plus à droite de n.

Par exemple, si n est 0010, n - 1 est 0001.

Ou, si n est 0110, n - 1 est 0101.

Remarque ête> Cela n'a pas d'importance si n - 1 introduit d'autres 1 car nous effectuons l'opération ET pour compter les bits définis.

Note

It does not matter whether n - 1 introduces other 1s because we are doing the AND operation to count the set bits.
For example, if n is 0000, then n - 1 is 0111. Their AND will be 0000.
Or, if n is 0010, then n - 1 is 0001. The rightmost set bit of n is 0 in n - 1, and that's all that matters.

Par exemple, si n est 0000, alors n - 1 est 0111. Leur ET sera 0000. Ou, si n est 0010, alors n - 1 est 0001. Le bit défini le plus à droite de n est 0 dans n - 1, et c'est tout ce qui compte.

Nous pouvons créer une boucle qui s'exécute tant qu'il y a 1 bits dans n, en comptant chacun au fur et à mesure. Aussi à chaque fois, on peut faire une opération ET

avec n et 1 de moins (n ​​& (n - 1)).

Une solution TypeScript simple ressemble à ceci :

function hammingWeight(n: number): number {
  let result = 0;
  while (n > 0) {
    n &= (n - 1);
    result++;
  }

  return result;
}

Note

We are using the bitwise AND assignment operator to assign the value to n.

Complexité temporelle et spatiale

La complexité temporelle est, je pense, $O(logn)$O(log n) — Dans le pire des cas, lorsque tous les bits sont définis, nous parcourrons la boucle $logn$log n fois (le nombre de bits dans la représentation binaire d'un nombre $n$n sera $logn$log n ).

La complexité spatiale sera constante ( $O(1)$O(1) ) car il n'y a pas d'utilisation de mémoire supplémentaire qui augmentera à mesure que l'entrée augmente.

---

Le prochain problème que nous examinerons est le comptage des bits. En attendant, bon codage.

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!