Des chiffres abominables

Un nombre est considéré comme impair s'il contient un nombre impair de un dans son expansion binaire. Les 10 premiers nombres impairs sont 1,2,4,7,10,11,13,14,16,19,21. Fait intéressant, toutes les puissances de 2 sont des nombres impairs car elles n’ont qu’un seul bit défini.

L'article suivant aborde en détail deux méthodes permettant de déterminer si un numéro est un numéro haineux.

Énoncé du problème

Le but de cette question est de vérifier si le nombre donné est un nombre odieux, c'est-à-dire s'il s'agit d'un nombre positif avec un nombre impair de bits définis dans son expansion binaire.

Exemples de nombres dégoûtants

Input: 34

Output: Non-Odious Number

Instructions

La représentation binaire de 34 est 10010.

Définissez le nombre de chiffres = 2.

Puisque le nombre de 1 est un nombre pair, 34 n'est pas un nombre terrible.

Input: 1024

Output: Odious Number

Instructions

La représentation binaire de 1024 est 10000000000.

Définissez le nombre de chiffres = 1.

Puisque 1024 est une puissance de 2, il n'y a qu'un seul bit de réglage. C'est donc un chiffre effrayant.

Input: 53

Output: Non-Odious Number

Instructions

(53)₁₀ = (110101)₂

Définissez le nombre de chiffres = 4.

Ce n’est donc pas un nombre abominable.

Solution

Afin de déterminer si un nombre est haineux, il faut savoir si le nombre de chiffres fixé est un nombre impair ou pair. La tâche principale ici est de compter le nombre de chiffres définis dans le développement binaire d'un nombre. La technique suivante peut être utilisée pour compter le nombre de chiffres, puis vérifier si le résultat est pair ou impair.

Approche Naive

Approche Naive

• Utilisez les opérateurs de boucle et de décalage vers la droite pour parcourir tous les chiffres du nombre un par un.

• Si la valeur du bit est 1, augmentez le nombre de un.

• Vérifiez si la valeur finale du nombre est impaire ou paire.

• Afficher les réponses.

pseudocode

Fonction no_of_set_bits()

• Nombre d'initialisations = 0

• quand (n > 0)

if ((n & 1) > 0)
   Increment count
Right Shift n

• Nombre de retours

Fonction is_odious()

• Si (le nombre est un nombre impair)

retour vrai

• Autres

erreur de retour

Fonction principale()

• Initialiser n

• Appel de fonction no_of_set_bits()

• Fonction d'appel is_odious()

• Impression

Exemple : programme C++

Ce programme vérifie si un numéro est offensant ou non. Il vérifie le bit le plus à droite à chaque itération de la boucle en décalant la valeur vers la droite de n à la fin de chaque itération dans la fonction no_of_set_bits().

#include<iostream>
using namespace std;
// this function counts the number of set bits by analyzing the rightmost bit using a while loop till n > 0.
// it performs logical & operation between 1 and n to determine if the rightmost bit is set or not.
// if it is set, count is incremented by 1
// right shift the value of n to make the bit left of the rightmost bit, the new rightmost bit.
int no_of_set_bits(int n){
   int count = 0;
   while (n > 0){
   
      // if the rightmost bit is 1: increment count
      if ((n & 1) > 0){
         count++;
      }
      
      // right shift the value of n to examine the next bit
      n = n >> 1;
   }
   return count;
}
// this function determines if count of set bits is odd or even
// odd -> odious
bool is_odious(int count){

   // if count is odd return true
   if (count % 2 != 0){
      return true;
   }
   return false;
}

// main function
int main(){
   int n = 27;
   int countBits = no_of_set_bits(n);
   if (is_odious(countBits)){
      cout << n << " is Odious Number";
   }
   else {
      cout << n << " is Non-Odious Number";
   }
   return 0;
}

Sortie

27 is Non-Odious Number

Analyse du temps et de l'espace

Complexité temporelle : O(log(n)), puisque l'expansion binaire de n nécessite log2n bits, nous vérifions tous les bits pour vérifier lesquels sont définis.

Complexité spatiale : O(1), car aucun espace supplémentaire n'est utilisé.

Méthode algorithmique de Brian Kernighan

Cet algorithme peut être utilisé pour calculer un nombre défini de chiffres dans un nombre de manière plus efficace. La fonction is_odious() peut alors être utilisée pour déterminer si le nombre est offensant.

Le principe de base de cette méthode est d'effacer à plusieurs reprises le bit le plus à droite du nombre tout en gardant une trace du nombre d'itérations nécessaires pour atteindre zéro. Les étapes impliquées sont -

• Initialiser le compte à 0

• Lorsque le nombre est supérieur à zéro, effectuez une opération au niveau du bit et entre le nombre et son complément à 2 pour désactiver le bit défini le plus à droite.

• Le décompte est incrémenté à chaque itération de boucle.

• Vérifiez si le décompte final est impair.

• Afficher les résultats.

Exemple

Soit le nombre 10. Le développement binaire de 10 est 1010. On constate qu'il dispose de 2 bits de réglage.

Itération de boucle 1 -

n = 10
n & (n-1) =  10 & 9
1010   (n)
1001   (n - 1)
1000   (n = 8)

Itération de boucle 2 -

n = 8
n & (n-1) = 8 & 7
1000    (n)
0111	(n-1)
0       (n = 0) 

Nombre d'itérations = nombre de réglages = 2.

pseudocode

Fonction no_of_set_bits()

• Nombre d'initialisations = 0

• quand (n > 0)

n = n & (n-1)

Augmenter le nombre

• Nombre de retours

Fonction is_odious()

Identique à la méthode précédente

Fonction principale()

Identique à la méthode précédente

Exemple : programme C++

Ce programme calcule le nombre de bits définis en comptant le nombre d'itérations nécessaires pour désactiver tous les bits définis. Pour annuler des bits, nous effectuons une opération ET au niveau du bit sur n et n-1. En effet, la représentation binaire de n-1 inverse le bit défini le plus à droite de n et tous les bits qui le suivent.

#include<iostream>
using namespace std;
// this function counts the number of set bits by unsetting the rightmost set bit using a while loop till n > 0.
// it performs logical & operation between n and n - 1 to unset the rightmost set bit.
// count is incremented in every iteration
int no_of_set_bits(int n){
   int count = 0;
   while (n > 0){
      // update the value of n to unset the current rightmost set bit
      n = n & (n - 1);
      count++;
   }
   return count;
}

// this function determines if count of set bits is odd or even
// odd -> odious
bool is_odious(int count){

   // if count is odd return true
   if (count % 2 != 0){
      return true;
   }
   return false;
}

// main function
int main(){
   int n = 27;
   int countBits = no_of_set_bits(n); // function call
   if (is_odious(countBits)){
      cout << n << " is Odious Number";
   }
   else {
      cout << n << " is Non-Odious Number";
   }
   return 0;
}

Sortie

27 is Non-Odious Number

Analyse espace-temps

Complexité temporelle - O(log(x)), où x est le nombre de chiffres définis dans le nombre. S'il n'y a qu'un seul bit défini, la boucle s'exécutera une fois.

Complexité de l'espace - O(1) puisqu'aucun espace supplémentaire n'est utilisé.

Comparez les méthodes ci-dessus

Bien que la première méthode soit assez facile à comprendre, elle nécessite des itérations log(n) pour produire le résultat final. La deuxième méthode, quant à elle, utilise l'itération log(x), où x est le nombre de chiffres défini dans le développement binaire du nombre. Cela améliore donc les performances.

Conclusion

Cet article aborde deux façons de vérifier si un numéro est dégoûtant. Il nous fournit également le concept de la méthode, des exemples, les algorithmes utilisés, les solutions du programme C++ et l'analyse de la complexité de chaque méthode. Il a également comparé les deux méthodes pour déterminer laquelle était la plus efficace.

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!