Bonsoir
Je voudrais générer des nombres binaires sur X bits contenant un nombre défini de "1".
Exp: un nombre binaire sur 12 bits contenant quatre "1": 101000100010
Svp, comment faire ?
Bonsoir
Je voudrais générer des nombres binaires sur X bits contenant un nombre défini de "1".
Exp: un nombre binaire sur 12 bits contenant quatre "1": 101000100010
Svp, comment faire ?
Bonjour,
Tu peux commencer avec un nombre F avec tous les bits à 0.
Tu peux générer un nombre N aléatoire entre 0 et X - 1 grâce à rand.
Puis regarder si le Nième bit de F est à 1 ou pas grâce à un mask F & (1 << N).
Si il est un 1 on retire un autre nombre sinon on l'ajoute grâce au même mask F |= 1 << N.
Cf la FAQ C.
N.B. F &= est équivalant à F = F &.
Peut être mon question n'est pas formulé bien.
Exactement, je voudrais l'equivalent de la fonction "randerr" en MATLAB
Exemple en Matlab
A = randerr(3,12,4)
Avec:
3 Nombre de generation
12 Taille du nombre généré
4 Nombre de "1" dans le nombre généré
Resultats possible de A
010010010100
100100010010
101000001001
Svp, comment faire la même chose en C++
Salut,
D'abord, il faut savoir que toute valeur se réduit, tôt ou tard, à une valeur binaire, car c'est la seule manière dont le processeur puisse la traiter.
Pour être plus précis : il n'existe strictement aucune différence entre une valeur binaire (0101010001), la même valeur décimale (337) et la même valeur hexadécimale (0x131), si ce n'est... la base utilisée pour leur représentation.
La base 2 (binaire) n'est qu'une représentation utilisable par le processeur, dans le sens où tout en informatique se limite peu ou prou à une succession d'interrupteurs qui peuvent, ou non, laisser passer le courent.
La base décimale est celle que l'humain a l'habitude de manipuler dans sa vie de tous les jours, mais la correspondance avec le binaire est difficile à faire dans le sens où il existe très peu de valeur correspondant à 10 exposant N qui correspondent à une valeur de 2 exposant M (il n'y en a d'ailleurs aucune, à ma connaissance )
La base hexadécimale est quant à elle une tentative de rendre la correspondante plus aisée, dans le sens ou une valeur binaire de 011100001110001010101010100111001 serait particulièrement difficile à évaluer "de tete".
Par contre, si l'on regroupe tous ces bits par groupe de 4, chaque groupe de bits permet de représenter 15 valeurs, et l'on a donc "plus facile" à se faire une idée de la valeur représentée.
Ainsi 1110 0001 1100 0101 0101 0101 0011 1001 (en binaire) se traduit-il en 0x E1C55539 en hexadécimal, et toutes deux équivalent la valeur 3 787 806 009 en décimale.
Tout cela pour en arriver à un fait bien particulier: il n'y a vraiment que lorsque tu souhaites pouvoir effectuer l'affichage d'une valeur particulière (ou, de manière plus générale, l'envoyer vers un flux formaté) que tu puisses avoir un intérêt quelconque à envisager de travailler avec des valeurs binaire ou hexadécimales, ou peu s'en faut.
L'une des exception est le cas où tu veux travailler avec un masque de bits.
C'est à dire que, pour une valeur donnée, chaque bit puisse représenter un état particulier qui ne puisse valoir que "vrai" ou "faux", et que les différents états ne sont pas (forcément) mutuellement exclusifs.
Mais à ce moment là, l'idéal est de créer une énumération qui utilise la rotation de bits pour définir la valeur de chaque état, proche de
(Nota : j'ai choisi de représenter les valeurs grace au décalage de bits, mais j'aurais aussi bien pu indiquer les valeurs équivalentes, en base 10 ou en hexadécimale )
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 enum State { etat1 = 1<<0, // équivaut à 2 exposant 0 soit 1 etat2 = 1<<1, // équivaut à 2 exposant 1 soit 2 etat3 = 1<<2, // équivaut à 2 exposant 2 soit 4 etat4 = 1<<3, // équivaut à 2 exposant 3 soit 8 etat5 = 1<<4, // équivaut à 2 exposant 4 soit 16 etat6 = 1<<5, // équivaut à 2 exposant 5 soit 32 etat7 = 1<<6, // équivaut à 2 exposant 6 soit 64 etat8 = 1<<7, // équivaut à 2 exposant 7 soit 128 etat9 = 1<<8, // équivaut à 2 exposant 8 soit 256 etat10 = 1<<9, // équivaut à 2 exposant 9 soit 512 etat11 = 1<<10, // équivaut à 2 exposant 10 soit 1024 etat12 = 1<<11, // équivaut à 2 exposant 11 soit 2048 etat13 = 1<<12, // équivaut à 2 exposant 12 soit 4096 }
A partir de là, si tu combine, d'une manière ou d'une autre, un certain nombre de ces états, tu es sur que la valeur représentée ne sera composée que de ce nombre précis de bits placés à 1
C'est la raison pour laquelle il arrive régulièrement que l'on définisse les opérateur &, | et ^ (ainsi que leur variantes &= |= et ^= ) pour les énumérations d'états, sous une forme plus ou moins proche de
De cette manière, en déclarant une variable de type State sous une forme proche de
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
18
19
20
21
22
23
24
25 inline State operator&(State a, State b) { return State (static_cast<int>(a) & static_cast<int>(b)); } inline State operator|(State a, State b) { return State (static_cast<int>(a) | static_cast<int>(b)); } inline State operator^(State a, State b) { return State (static_cast<int>(a) ^ static_cast<int>(b)); } inline State operator~(State a) { return State (~static_cast<int>(a)); } inline State & operator|=(State & a, State b) { return a = a | b; } inline State & operator&=(State & a, State b) { return a = a & b; } inline State & operator^=(State & a, State b) { return a = a ^ b; }
tu te retrouves avec une valeur dans laquelle quatre bits sont mis à 1, les autres étant mis à 0, et tu peux t'assurer que les bits sont mis à 1 avec un code proche de
Code : Sélectionner tout - Visualiser dans une fenêtre à part State etat(etat1 | etat12 |etat3 |etat10); // hé oui, l'ordre n'a aucune importance ;)
De même, si tu prends, selon l'exemple de State que j'ai donné, n'importe quelle valeur comprise entre 0 et 8191 (ce qui correspond en binaire à 0111111111111 ), tu pourrais utiliser un code proche de
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10 if( etat & etat1) // etat1 est à 1 { } if(etat & etat12) // etat12 est à 1 { } if(etat & etat4) //etat4 est à 1 (faux dans le cas de l'exemple :D ) { } /* .... */et obtenir un masque de bits "cohérent".
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 int i = (n'importe quelle valeur comprise entre 0 et 8191); State etat(i);
Si, maintenant, tu veux obtenir un nombre précis de bits placés à 1, le mieux est de compter ceux que tu places à 1 sous une forme proche de
Et si tu veux, une fois que tu as tout cela, toujours obtenir une représentation en binaire de ton état, l"idéal est de passer par la classe bitset, qui est prévue pour cela, sous une forme proche de
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11 State state(0); // tous les bits à 0 int count = 0; // aucun bit n'est à 1 :D while(count < NOMBRE_DEBITS_SOUHAITES) { int num = 1<< (rand()%12); if(!(state & num)) // si le bit "num" est à 0 { state |= State(num); ++ count; } }
voire, si tu veux récupérer une valeur décimale sur base d'une chaine représentant la valeur binaire d'un nombre, sous la forme de
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2 std::bitset<12> binary(valeur_a_convertir); // !!! valeur maximale : 2 exposant 12 - 1 :D std::cout<<"representation binaire de la valeur :"<<binary.to_string();
Maintenant, les trois derniers codes que j'ai donnés s'appliquent aussi bien à des valeurs énumérées qu'à tout type primitif "de taille suffisante" pour représenter le nombre de bits qui t'intéresse
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2 std::bitset<12> toValue("10110111"); std::cout<<"représentation numérique de la chaine "<<toValue.tu_uloong();
A méditer: La solution la plus simple est toujours la moins compliquée
Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
Compiler Gcc sous windows avec MinGW
Coder efficacement en C++ : dans les bacs le 17 février 2014
mon tout nouveau blog
Intuitivement, je vois deux algorithmes qui peuvent aller :
- Celui proposé par koala, où tu mets aléatoirement des bits à 1 jusqu’à ce que tu en aies le bon nombre
- Un algorithme où tu pars d'un nombre ayant le bon nombre de bits à 1, puis un réordonnancement aléatoire des bits (http://en.wikipedia.org/wiki/Knuth_shuffle)
J'imagine que s'il y a peu de bits à 1, la première méthode est plus rapide, mais s'il y en a beaucoup, la seconde peut gagner. Elle a en tout cas l'avantage d'être en temps constant. Il faudrait tester...
Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.
Windows only, je sais pas récupérer le temps sous la seconde de manière portable.
Résultats en pièce jointe. (moyenne de 2000 tests à chaque coup)
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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145 #include <iostream> #include <bitset> #include <ctime> #define WIN32_LEAN_AND_MEAN #include <Windows.h> typedef unsigned int uint; const uint nbTests = 2000; double freq; template <uint nb> std::bitset<nb> koala(int i) { std::bitset<nb> ret(0); int count = 0; while(count < i) { size_t bitAt = (size_t)(rand() % nb); if(!ret.at(bitAt)) { ret.set(bitAt); ++count; } } return ret; } template <uint nb> std::bitset<nb> knuthShuffle(int i) { std::bitset<nb> ret(0); for(int ii=0; ii<i; ++ii) { ret.set(ii); } for(int ii=0; ii<nb; ++ii) { size_t bitAt = (size_t)(rand() % (nb - ii)); bool b = ret.at(bitAt); ret.at(bitAt) = ret.at(nb - ii - 1); ret.at(nb - ii - 1) = b; } return ret; } struct Result { double koala25, koala50, koala75; double knuthShuffle25, knuthShuffle50, knuthShuffle75; int nb; }; std::ostream& operator<<(std::ostream& o, const Result& r) { // affichage structuré pour excel o << "koala " << r.nb << " " << r.koala25 << " " << r.koala50 << " " << r.koala75 << "\n" << "knuthShuffle " << r.nb << " " << r.knuthShuffle25 << " " << r.knuthShuffle50 << " " << r.knuthShuffle75 << std::endl; return o; } template <uint nb> inline void fail(const std::bitset<nb>& bs, const std::string& m, int target) { if(bs.count() != target) { std::cerr << m << " fail (" << nb << " " << target << ")" << std::endl; exit(1); } } template <uint nb> Result test(int iter) { Result ret; ret.nb = nb; LARGE_INTEGER begin, end; int n25 = (int)(nb * 0.25); int n50 = (int)(nb * 0.5); int n75 = (int)(nb * 0.75); const std::string n1 = "koala", n2 = "knuthShuffle"; // koala QueryPerformanceCounter(&begin); for(int i=0; i<iter; ++i) { fail(koala<nb>(n25), n1, n25); } QueryPerformanceCounter(&end); ret.koala25 = ((double)(end.QuadPart - begin.QuadPart)) / freq; QueryPerformanceCounter(&begin); for(int i=0; i<iter; ++i) { fail(koala<nb>(n50), n1, n50); } QueryPerformanceCounter(&end); ret.koala50 = ((double)(end.QuadPart - begin.QuadPart)) / freq; QueryPerformanceCounter(&begin); for(int i=0; i<iter; ++i) { fail(koala<nb>(n75), n1, n75); } QueryPerformanceCounter(&end); ret.koala75 = ((double)(end.QuadPart - begin.QuadPart)) / freq; // knuthShuffle QueryPerformanceCounter(&begin); for(int i=0; i<iter; ++i) { fail(knuthShuffle<nb>(n25), n2, n25); } QueryPerformanceCounter(&end); ret.knuthShuffle25 = ((double)(end.QuadPart - begin.QuadPart)) / freq; QueryPerformanceCounter(&begin); for(int i=0; i<iter; ++i) { fail(knuthShuffle<nb>(n50), n2, n50); } QueryPerformanceCounter(&end); ret.knuthShuffle50 = ((double)(end.QuadPart - begin.QuadPart)) / freq; QueryPerformanceCounter(&begin); for(int i=0; i<iter; ++i) { fail(knuthShuffle<nb>(n75), n2, n75); } QueryPerformanceCounter(&end); ret.knuthShuffle75 = ((double)(end.QuadPart - begin.QuadPart)) / freq; return ret; } template <uint nb, uint n2, uint... nbs> void multiTest() { std::cout << test<nb>(nbTests); multiTest<n2, nbs...>(); } template <uint nb> void multiTest() { std::cout << test<nb>(nbTests); } int main (int argc, char* argv[]) { srand((uint)time(nullptr)); LARGE_INTEGER lfreq; QueryPerformanceFrequency(&lfreq); freq = ((double)lfreq.QuadPart) / 1000000.0 * nbTests; // µs multiTest<1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 11000, 12000, 13000, 14000, 15000, 16000, 17000, 18000, 19000, 20000>(); return 0; }
Les pourcentages indique le nombre de bit à mettre à 1, exemple sur un bitset de taille 1000, 25% indique qu'on veut 250 bits à 1.
Il est évidemment inutile de dépasser 50% (dans ce cas il vaut mieux inverser l'algo et placer des 0), mais c'était pour voir la corrélation entre nombre de 1 à placer et temps d'exec.
Bien vu !
Autre approche, un set<int> dans lequel tu stoque des entiers aléatoires entre 0 et la taille du nombre à générer, tant que le set n'a pas autant d'entrées que le nombre de 1 voulus.
Puis convertir via des décalages.
Mes principes de bases du codeur qui veut pouvoir dormir:Pour faire des graphes, essayez yEd.
- Une variable de moins est une source d'erreur en moins.
- Un pointeur de moins est une montagne d'erreurs en moins.
- Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
- jamais signifie "sauf si j'ai passé trois jours à prouver que je peux".
- La plus sotte des questions est celle qu'on ne pose pas.
le ter nel est le titre porté par un de mes personnages de jeu de rôle
Je constates quand meme avec plaisir au vu du graphique que, même si je n'ai donné qu'une implémentation naïve (et, pour tout dire, assez peu réfléchie), il s'agit sans doute de l'implémentation la plus efficace, même si elle n'est pas en temps constant
Cela semble confirmer ce que je dis toujours : la solution la plus simple est toujours la moins compliquée
A méditer: La solution la plus simple est toujours la moins compliquée
Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
Compiler Gcc sous windows avec MinGW
Coder efficacement en C++ : dans les bacs le 17 février 2014
mon tout nouveau blog
Simplicity is in the eye of the beholder...
Dit autrement, je trouve à la base ta solution plus complexe que la mienne en terme de compréhension comme en terme d'extensibilité (imagine par exemple si en base 10, on voulait avoir n fois chaque chiffre), la mienne n'étant qu'un cas particulier de mélange où l'on défini correctement les conditions initiales.
Ce n'est pas pour dire qu'elle est moins bonne, elle ne n'est clairement pas. Juste pour dire que la simplicité est un critère subjectif, qui ne peut hélas pas vraiment être utilisé pour faire un choix.
Sinon, je suis persuadé qu'il est possible d'optimiser les manipulations de bits dans l'implémentation de ces solutions, mais ça ne servirait pas à grand-chose, puisqu'au final une différence importante est que dans ta solution, on génère en moyenne moins de nombre aléatoires que dans la mienne (ce qui ne serait plus vrai avec les extensions du problème).
Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager