puissance 2 en C++ Fermé

Question

Bonjour, comment savoir si un entier est une puissance de 2 avec C++, sans faire de boucle, juste avec les opérateurs: + - * / % et manipulation de bit ~ ^ | & >> << ... merci de votre aide

jk · Accepted Answer

Résumé :

if( ((x&(x-1)) != 0) || (x == 0) )
            //pas puissance de deux
else
            //puissance de deux


Ou bien :


if(   (((x & -x) xor x) == 0)  &&  (x != 0)    ){
            //x est puissance de 2
}else{
            //x n'est pas puissance de 2
} 

Ou encore :

if( ((x ^ (x-1)) == x+(x-1)) && (x != 0) ) 
          printf("x puissance de 2"); 


Le tout testé jusqu'à 2^13

jisisv · Answer

Un truc tout con fait à la va-vite


johand@horus:~/src/cpp$ cat ispow2.cpp 
#include <stdlib.h>
#include <stdio.h>
int main(int aegc, char *argv[])
{	
	int val,cnt,bit=1;
	val = atoi(argv[1]);
	if ( 0 == val )
	{
		return 1;
	}
	for( cnt=0; cnt < 16; cnt++)
	{
		if ( val ==bit )
		{
			return 0;
		}
		bit <<= 1 ;
	}
	return 1;
}
johand@horus:~/src/cpp$ for i in $(seq 0 32) ; do echo -n "$i " ; ./ispow2  $i  ; echo $? ; done
0 1
1 0
2 0
3 1
4 0
5 1
6 1
7 1
8 0
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 0
17 1
18 1
19 1
20 1
21 1
22 1
23 1
24 1
25 1
26 1
27 1
28 1
29 1
30 1
31 1
32 0

vignemail1 · Answer

si tu as log tu peux voir si log(n)/log(2) est un entier

redred · Answer

Merci  jisisv
mais moi je veux un programme sans boucle, un truc simple sur une seule ligne.

Char Snipeur · Answer

C'est simple, réfléchi en binaire.
Tu veux savoir si ton entier est une puissance de 10 (deux en binaire).
Rien de plus simple, 10^n donne un 1 avec n zéro derrière !
Donc il suffit de faire un ou exclusif entre chaque bit. Mais sans faire de boucle c'est pas évident ! ça fait une ligne super longue. disons que ton entier I est sur 8 bits (un char) et que utilise la notation binaire, ça donne un ruc dans le genre :
if( (00000001&I)^(00000010&I)^(00000100&I)^(00001000&I)^(00010000&I)^(00100000&I)^(01000000&I)^(10000000&I) ) printf("puissance de deux");
else printf("pas une puissance de deux");

Sinon, avec une boucle de manière plus générique :

bool test=false;
for (int i=0;i<sizeof(I)*8;++i)
  {
   test=(1&I)^test;
   I<<1; // à tester le décalage de bit, c'est peut être I>>1
   }
if(test)//puissance de 2
else //bas non !

fiddy · Answer

Bien trouvé.
Oui, ça marche. Mathématiquement correct ;)

Char Snipeur · Answer

Salut.
si ça fonctionne, super bien joué ! (je ne suis pas capable de juger facilement si c'est juste)
Par contre, pour jouer mon rabats joie, le complément à deux dépend de l'implémentation du bazar, j'ai un doute sur l'universalité de cette méthode. Si quelqu'un sait.

arkan · Answer

Salut,

Si x est une puissance de deux alors x-1 est de la forme 111..  ...11
Donc non_bit_à_bit(x-1) == 0 (Si x puissance de deux)


if(   (~(x-1)) == 0 && x > 0  ){
      //alors puissance de deux
}



N.B:  

(0-1) = -1
Or -1 en complément à 2 égal 1111111111111111 

Donc il faut que x soit strictement positif pour être sûr de notre coup

Puissance 2 en C++

8 réponses

Discussions similaires