Quelle est la manière la plus simple de tester si un nombre est une puissance de 2 en C ++?

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ù trouver ce type d'algorithme?

(n & (n - 1)) == 0est le meilleur. Cependant, notez qu'il retournera incorrectement true pour n = 0, donc si cela est possible, vous voudrez le vérifier explicitement.

http://www.graphics.stanford.edu/~seander/bithacks.html a une grande collection d'algorithmes astucieux de twiddling de bits, y compris celui-ci.

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

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

Fonctionnera très bien; un de moins qu'une puissance de deux correspond à tous les 1 dans les bits les moins significatifs, il faut donc ET à 0 au niveau du bit.

Comme je supposais des nombres non signés, le test == 0 (que j'avais oublié à l'origine, désolé) est adéquat. Vous pouvez souhaiter un test> 0 si vous utilisez des entiers signés.

Les puissances de deux en binaire ressemblent à ceci:

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

Notez qu'il y a toujours exactement 1 bit défini. La seule exception concerne un entier signé. Par exemple, un entier signé de 8 bits avec une valeur de -128 ressemble à:

10000000

Donc, après avoir vérifié que le nombre est supérieur à zéro, nous pouvons utiliser un petit hack astucieux pour tester qu'un seul bit est défini.

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

Pour plus de twiddling, voir ici .

Approche n ° 1:

Divisez le nombre par 2 en reclus pour le vérifier.

Complexité temporelle: O (log2n).

Approche n ° 2:

Au niveau du bit ET le nombre avec son numéro juste précédent doit être égal à ZERO.

Exemple: Nombre = 8 Binaire de 8: 1 0 0 0 Binaire de 7: 0 1 1 1 et le ET au niveau du bit des deux nombres est 0 0 0 0 = 0.

Complexité temporelle: O (1).

Approche n ° 3:

XOR au niveau du bit, le nombre avec son numéro précédent doit être la somme des deux nombres.

Exemple: Nombre = 8 Binaire de 8: 1 0 0 0 Binaire de 7: 0 1 1 1 et le XOR au niveau du bit des deux nombres est 1 1 1 1 = 15.

Complexité temporelle: O (1).

http://javaexplorer03.blogspot.in/2016/01/how-to-check-number-is-power-of-two.html

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

pour toute puissance de 2, ce qui suit vaut également.

n & (- n) == n

REMARQUE: La condition est vraie pour n = 0, bien que ce ne soit pas une puissance de 2. La
raison pour laquelle cela fonctionne est:
-n est le complément 2s de n. -n aura chaque bit à gauche du bit le plus à droite de n inversé par rapport à n. Pour les puissances de 2, il n'y a qu'un seul bit défini.

En C ++ 20, std::ispow2vous pouvez utiliser exactement ce but si vous n'avez pas besoin de l'implémenter vous-même:

#include <bit>
static_assert(std::ispow2(16));
static_assert(!std::ispow2(15));

C'est probablement le plus rapide, si vous utilisez GCC. Il utilise uniquement une instruction de processeur POPCNT et une comparaison. Représentation binaire de toute puissance de 2 nombres, a toujours un seul bit défini, les autres bits sont toujours zéro. Nous comptons donc le nombre de bits définis avec POPCNT, et s'il est égal à 1, le nombre est une puissance de 2. Je ne pense pas qu'il y ait de méthodes plus rapides possibles. Et c'est très simple, si vous l'avez compris une fois:

if(1==__builtin_popcount(n))

Le suivi serait plus rapide que la réponse la plus votée en raison du court-circuit booléen et du fait que la comparaison est lente.

int isPowerOfTwo(unsigned int x)
{
  return x && !(x & (x – 1));
}

Si vous savez que x ne peut pas être 0 alors

int isPowerOfTwo(unsigned int x)
{
  return !(x & (x – 1));
}

return n > 0 && 0 == (1 << 30) % n;

Quelle est la manière la plus simple de tester si un nombre est une puissance de 2 en C ++?

Si vous disposez d'un processeur Intel moderne avec les instructions de manipulation des bits , vous pouvez effectuer les opérations suivantes. Il omet le code C / C ++ simple car d'autres y ont déjà répondu, mais vous en avez besoin si l'IMC n'est pas disponible ou activé.

bool IsPowerOf2_32(uint32_t x)
{
#if __BMI__ || ((_MSC_VER >= 1900) && defined(__AVX2__))
    return !!((x > 0) && _blsr_u32(x));
#endif
    // Fallback to C/C++ code
}

bool IsPowerOf2_64(uint64_t x)
{
#if __BMI__ || ((_MSC_VER >= 1900) && defined(__AVX2__))
    return !!((x > 0) && _blsr_u64(x));
#endif
    // Fallback to C/C++ code
}

Prise en charge de l'IMC des signaux GCC, ICC et Clang avec __BMI__. Il est disponible dans les compilateurs Microsoft dans Visual Studio 2015 et versions ultérieures lorsque AVX2 est disponible et activé . Pour les en-têtes dont vous avez besoin, voir Fichiers d'en-tête pour les intrinsèques SIMD .

Je garde généralement le _blsr_u64avec un _LP64_en cas de compilation sur i686. Clang a besoin d'une petite solution de contournement car il utilise un nom de symbole intrinsèque légèrement différent:

#if defined(__GNUC__) && defined(__BMI__)
# if defined(__clang__)
#  ifndef _tzcnt_u32
#   define _tzcnt_u32(x) __tzcnt_u32(x)
#  endif
#  ifndef _blsr_u32
#    define  _blsr_u32(x)  __blsr_u32(x)
#  endif
#  ifdef __x86_64__
#   ifndef _tzcnt_u64
#    define _tzcnt_u64(x) __tzcnt_u64(x)
#   endif
#   ifndef _blsr_u64
#     define  _blsr_u64(x)  __blsr_u64(x)
#   endif
#  endif  // x86_64
# endif  // Clang
#endif  // GNUC and BMI

Pouvez-vous me dire un bon site Web où trouver ce type d'algorithme?

Ce site est souvent cité: Bit Twiddling Hacks .

Ce n'est pas le moyen le plus rapide ou le plus court, mais je pense qu'il 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 puisque le binaire est basé sur des puissances de deux. Tout nombre avec un seul bit défini doit être une puissance de deux.

Voici une autre méthode, dans ce cas en utilisant |au lieu de &:

bool is_power_of_2(int x) {
    return x > 0 && (x<<1 == (x|(x-1)) +1));
}

C'est possible via c ++

int IsPowOf2(int z) {
double x=log2(z);
int y=x;
if (x==(double)y)
return 1;
else
return 0;
}

Je sais que c'est un très vieux message, mais j'ai pensé qu'il pourrait être intéressant de le publier ici.

De Code-Golf SE (donc tout le crédit à celui (s) qui a écrit ceci): Showcase of Languages

(Paragraphe sur C , sous-paragraphe Longueur 36 extrait )

bool isPow2(const unsigned int num){return!!num&!(num&(num-1));}

Une autre façon de procéder (peut-être pas la plus rapide) est de déterminer si ln (x) / ln (2) est un nombre entier.

Voici la méthode de décalage de bits dans T-SQL (SQL Server):

SELECT CASE WHEN @X>0 AND (@X) & (@X-1)=0 THEN 1 ELSE 0 END AS IsPowerOfTwo

C'est beaucoup plus rapide que de faire un logarithme quatre fois (premier ensemble pour obtenir un résultat décimal, 2ème ensemble pour obtenir un ensemble d'entiers et comparer)