Discussion :

[kimikou]

Bonsoir,

Si on prend deux nombres binaires a et b, comment faire une fonction qui teste si b est inclus dans a ? avec une complexité O(1).

Merci d'avance.

[Obsidian]

On relit son cours ? /o\

[kimikou]

Pouvez-vous m'indiquer l'endroit où trouver mon bonheur ?

[Mat.M]

Bonsoir,

Si on prend deux nombres binaires a et b, comment faire une fonction qui teste si b est inclus dans a ? avec une complexité O(1).

Merci d'avance.

un nombre binaire je tiens à préciser c'est une représentation

tu peux passer par une représentation sous forme de chaîne de caractères.

Ensuite pour comparer deux binaires il suffit de faire un simple masque AND.

Par exemple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
char chaine1[]="0101";
char chaine2[]="1101";
char *ptr1=chaine1;
char *ptr2=chaine2;
int valeurBinaire1;
int valeurBinaire2;
while( *ptr1 !='\0')
{
 valeurBinaire1=atoi(*ptr1);
 valeurBinaire2=atoi(*ptr2);
if( valeurBinaire1 & valeurBinaire2)
{// faire quelque chose
}
 
ptr1++;ptr2++;
}

c'est un exemple de code à titre de suggestion il n'est peut-être pas bon mais il donne une certaine logique...

voir aussi la possibilité avec des champs de bits...

[matafan]

Qu'est-ce que tu entends exactement par "inclus dans" ?

[kimikou]

Par exemple, a=0101 est inclus dans b=0111. Car les deux 1 présents dans a sont présents dans b. Cela est possible en vérifiant si a & b == a.


De même j'aimerai vérifier en temps constant si un nombre binaire ne possède qu'un seul 1. Y a t-il une méthode ? En utilisant des opérateurs binaires de préférence.

Par exemple la fonction me renvoi vrai pour 0100 et faux pour 1010.

[matafan]

Tout ce qu'il faut savoir sur le comptage de bits :
http://en.wikipedia.org/wiki/Hamming_weight

[diogene]

De même j'aimerai vérifier en temps constant si un nombre binaire ne possède qu'un seul 1. Y a t-il une méthode ? En utilisant des opérateurs binaires de préférence.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
unsigned int n = ....;
if(n!=0 && (n&(n-1))== 0).... 
     // la représentation binaire de n ne comporte qu'un 1
     // (n est puissance de deux)