Quel est le moyen le plus simple de tester si un nombre est une puissance de 2 en C ++?

Question

J'ai besoin d'une fonction comme celle-ci:

 // return true iff 'n' is a power of 2, e.g.
// is_power_of_2(16) => true  is_power_of_2(3) => false
bool is_power_of_2(int n);
 

Quelqu'un peut-il suggérer comment je pourrais écrire ceci? Pouvez-vous me dire un bon site web où ce type d'algorithme peut être trouvé?

Answer 1

"(n & (n - 1)) == 0" est le meilleur. Toutefois, notez qu'il renverra incorrectement la valeur true pour n = 0; par conséquent, si cela est possible, vous souhaiterez le vérifier explicitement.

http://www-graphics.stanford.edu/~seander/bithacks.html possède une vaste collection d'algorithmes astucieux, notamment celui-ci.

Answer 2

Une puissance de deux n'aura qu'un bit défini (pour les nombres non signés). Quelque chose comme

 bool powerOfTwo = !(x == 0) && !(x & (x - 1));
 

Fonctionnera bien; un de moins qu'une puissance de deux correspond à tous les 1 dans les bits les moins significatifs, ainsi doit ET à 0 bits.

Comme je supposais des nombres non signés, le test == 0 (que j'avais initialement oublié, désolé) est adéquat. Vous voudrez peut-être un test> 0 si vous utilisez des entiers signés.

Answer 3

Les puissances de deux, en binaire, ressemble à ceci:

1: 0001
2: 0010
4: 0100
8: 1000

Notez qu'il y a toujours exactement 1 ensemble de bits. La seule exception est avec un entier signé. par exemple, Un 8 bits entier signé avec une valeur de -128 ressemble:

10000000

Donc, après avoir vérifié que le nombre est supérieur à zéro, on peut utiliser un astucieux petit peu de bidouille pour tester qu'un et un seul bit est défini.

bool is_power_of_2(int x) {
    return x > 0 && !(x & (x−1));
}

Pour plus de bits se tourner les voir ici.

Answer 4

bool is_power_of_2(int i) {
    if ( i <= 0 ) {
        return 0;
    }
    return ! (i & (i-1));
}

Answer 5

Ce n'est pas le moyen le plus rapide ou le plus rapide, mais je pense que c'est très lisible. Donc je ferais quelque chose comme ça:

 bool is_power_of_2(int n)
  int bitCounter=0;
  while(n) {
    if ((n & 1) == 1) {
      ++bitCounter;
    }
    n >>= 1;
  }
  return (bitCounter == 1);
}
 

Cela fonctionne car le binaire est basé sur des puissances de deux. Tout nombre avec un seul bit défini doit être une puissance de deux.