Puissance 2 en C++

Réponse 2 / 8

vignemail1 Messages postés 1246 Date d'inscription vendredi 8 octobre 2004 Statut Contributeur Dernière intervention 13 septembre 2019 259
30 juin 2008 à 22:40

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

jisisv Messages postés 3645 Date d'inscription dimanche 18 mars 2001 Statut Modérateur Dernière intervention 15 janvier 2017 934
30 juin 2008 à 22:51

Si ce que tu dis est mathématiquement correct , c'est
* innefficace sur in ordinateur (utilisation de bibliothèques; du coprocesseur...)
*vu les erreurs d'arrondi ce rapport ne sera jamais un entier , bien que très proche d'un entier

Johan

Réponse 3 / 8

jisisv Messages postés 3645 Date d'inscription dimanche 18 mars 2001 Statut Modérateur Dernière intervention 15 janvier 2017 934
30 juin 2008 à 22:33

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

Réponse 4 / 8

redred
1 juil. 2008 à 00:04

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

jisisv Messages postés 3645 Date d'inscription dimanche 18 mars 2001 Statut Modérateur Dernière intervention 15 janvier 2017 934
2 juil. 2008 à 18:53

Tu demandes à INTEL et MD et.SUN.. de fournur une instruction assembleur btcnt qui retrourne le nombre de bits non nuls d'un octet, mot ; dword, Notons que je n'ai pas vrifi. Elle existe peut-être.qword. ....

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question

Réponse 5 / 8

Char Snipeur Messages postés 9696 Date d'inscription vendredi 23 avril 2004 Statut Contributeur Dernière intervention 3 octobre 2023 1 297
1 juil. 2008 à 09:00

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 !

Marco17
19 oct. 2008 à 20:53

Euh, je me demandais si cette solution ne serait pas bonne ... :

//Pour savoir si x est une puissance de 2...
// x est en notation binaire en complément à deux

if( ((x & -x) xor x) == 0){
//x est puissance de 2
}else{
//x n'est pas puissance de 2
}

Si quelqu'un peut me dire si cette solution là fonctionne... Ca serait sympa, j'ai pas trouvé de contre-exemple pour le moment.

Réponse 6 / 8

fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 836
19 oct. 2008 à 22:17

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

Réponse 7 / 8

Char Snipeur Messages postés 9696 Date d'inscription vendredi 23 avril 2004 Statut Contributeur Dernière intervention 3 octobre 2023 1 297
20 oct. 2008 à 08:54

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.

Réponse 8 / 8

arkan
7 juin 2010 à 09:05

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

jk
7 juin 2010 à 09:42

Marche pas : x-1 est de la forme 0000111 plutôt XD

jk
7 juin 2010 à 09:51

Je propose :

unsigned int x;

    for( x = 0; x<=4096; x++){
        if( ((x&(x-1)) != 0) || (x == 0) )
            std::cout <<"NON " << x << "\n";
        else
            std::cout <<"     OUI " << x << "\n";
    }

fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 836
7 juin 2010 à 11:40

A jk
c'est bien de proposer, mais lenoncé est très simple : pas de boucle.
For est une boucle.
La solution a déjà été donnée en utilisant xor et la complémentarité.
Cdlt

Char Snipeur Messages postés 9696 Date d'inscription vendredi 23 avril 2004 Statut Contributeur Dernière intervention 3 octobre 2023 1 297
7 juin 2010 à 11:43

je dirai plutôt :
if( x ^ (x-1) == x+(x-1) ) printf("x puissance de 2");
sans jurer de la fiabilité

jk
8 juin 2010 à 16:06

fiddy : lit moins vite ^^
ma boucle est juste là pour montrer que au mois ça marche
pour un nombre de 0 à 4096.
l'algorithme pour savoir si c'est une puissance de deux ce résume au if !
(j'ai juste copier mon test à la bourrin sans retirer le for)

Snippeur :
Ta solution est bonne au moins jusqu'à 4096 xD (j'ai testé)
Par contre en C il faut les parenthèse :

(x ^ (x-1)) == (x+(x-1))

car le xor à une priorité très faible plus faible que ==
Ha et il faut penser à gérer le cas particulier x == 0 car ce n'est pas une puissance de deux ^^

Puissance 2 en C++

8 réponses

Discussions similaires

Newsletters