Generation des nombres binaires

Version imprimable

10/03/2013, 16h24
hassen.km

Generation des nombres binaires

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 ?
10/03/2013, 16h40
Neckara

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 &.
10/03/2013, 17h52
hassen.km

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 :aie:)

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
Code:

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 }
(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 :D)

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 ^= :D) pour les énumérations d'états, sous une forme plus ou moins proche de
Code:

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; }
De cette manière, en déclarant une variable de type State sous une forme proche de

Code:

State etat(etat1 | etat12 |etat3 |etat10); // hé oui, l'ordre n'a aucune importance ;)

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:

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 ) { } /* .... */
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:

1 2 3 int i = (n'importe quelle valeur comprise entre 0 et 8191); State etat(i);
et obtenir un masque de bits "cohérent".

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
Code:

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; } }
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:

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();
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:

1 2 std::bitset<12> toValue("10110111"); std::cout<<"représentation numérique de la chaine "<<toValue.tu_uloong();
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 ;)

10/03/2013, 19h20
JolyLoic

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...

1 pièce(s) jointe(s)

Citation:

Envoyé par JolyLoic

Il faudrait tester...

Windows only, je sais pas récupérer le temps sous la seconde de manière portable. :aie:

Code:

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;
}

Résultats en pièce jointe. (moyenne de 2000 tests à chaque coup)
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.

Citation:

Envoyé par JolyLoic

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.

Bien vu ! :)

11/03/2013, 10h43
ternel

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.
12/03/2013, 03h33
koala01

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 :D

Cela semble confirmer ce que je dis toujours : la solution la plus simple est toujours la moins compliquée :D
12/03/2013, 08h12
JolyLoic

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).