Discussion :

[Kaluza]

Bonjour.

J'ai un problème assez simple et j'aimerai savoir quelle est la méthode la plus rapide (pas la méthode naive qui consiste à diviser mon nombre par des puissances successives de 2) pour remplir un tableau de booléens à partir de la représentation binaire d'un nombre.

J'ai :

Code :

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

1
2
unsigned long long int n // (entier 64 bits)
bool nbinary[64]

et je veux remplir nbinary selon la représentation binaire de n (et je veux quelque chose de portable quelque soit l'endianness du système (par exemple nbinary[3] sera toujours associé à 2^3)).

Par exemple pour n = 13 (en base 2 : 1101), j'aurai :

Code :

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

1
2
3
4
5
nbinary[0] = true; 
nbinary[1] = false; 
nbinary[2] = true; 
nbinary[3] = true; 
nbinary[4] jusqu'à nbinary[63] = false;

Merci beaucoup

[BlueMonkey]

Bonjour,

Je veux quelque chose de portable quelque soit l'endianness du système

On oublie donc le C brut avec des champs de bits.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
typedef union
{
 unsigned long long value;
 struct
 {
    bool b0:1;
    bool b1:1;
    //..
    bool b62:1;
    bool b63:1;
 };
}Int64ToBits;

( je rigole)

Dans ce cas pourquoi pas la STL et sa bitset


Et si c'est pas assez rapide, pourquoi faire un tableau de boolean ?
Faire simplement le test sur l'entier avec les opérations binaires <valeur> & <mask> n'est ce pas suffisant ?
mask = 1 << <position du bit à tester>;
bool : true = toute valeur différente de 0

[aquaz]

Si le but est vraiment de remplir un tableau de booleens, tu vas bien être obligé de faire des multiplications ou des divisions par 2 pour obtenir individuellement les bits. Mais bon comme une division ou une multiplication par 2 est instantanée(c'est un bitshift, quand on fait a / 2 le compilateur fait a >> 1 et a * 2 se transforme en a << 1 avec les optimisations). Je vois pas vraiment comment on peut avoir plus rapide que ça:

Code :

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

1
2
3
4
5
6
7
8
9
 
int a = 13;
bool b[32];
int n = 0;
for (n = 0; n < 32; ++n)
{
	b[n] = a & 1;
	a >>= 1;
}

[Bousk]

Pourquoi ne pas réaliser un simple mask ?
Ca permet de garder le nombre initial pour les calculs, sans devoir reparser les booleans et le recréer.
Et c'est instantané.

Code :

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

#define GETBIT(a,n) ((1<<(n))&(a))

[Ekleog]

Et en plus, c'est très probablement plus rapide qu'une recherche dans un tableau de booléens, même stockés en mémoire. (histoire de variable registre)