Nombre de bits à 1 dans un unsigned / index du 1er bit à 1

J'ai écrit un programme de Sudoku en C

Celui-ci utilise intensivement les deux macros suivantes :

Code:

---

1 2 3 4

// x est un unsigned dont seuls les 16 premiers bits peuvent etre a 1 #define Count_bit(x) (count_bit[x]) // nb de bits a 1 ds x #define First_bit(x) (first_bit[x]) // numero du premier bit a 1 ds x

---

Deux tableaux de 2^16=65536 unsigned char sont precalcules et me permettent d'obtenir les valeurs voulues :

Code:

---

1 2	unsigned char count_bit[65536] unsigned char first_bit[65536]

---

Le pb est que la consultation de ces tables est couteux en temps d'execution !
Je sais qu'il existe une instruction x86 pour l'index du premier bit a 1 : bsf ...
Mais je ne m'y connais pas assez en assembleur.

J'aurai besoin du code assembleur pour ces 2 fonctions (dans le but de le copier-coller dans mon prog (sous Visual C++ 6)) ...

Merci d'avance ...

Bonjour,

voilà ce que j'ai pondu :D

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

#include <iostream>   unsigned int GetFirstBitAt1 (unsigned int x); unsigned int CountBitAt1 (unsigned int x);   #define Count_bit(x) (CountBitAt1 (count_bit[x])) // nb de bits a 1 ds x #define First_bit(x) (GetFirstBitAt1 (first_bit[x])) // numero du premier bit a 1 ds x   using namespace std;   int main() { unsigned char first_bit[]= {1, 4, 0x80};// en binaire: 1, 100, 10000000 unsigned char count_bit[] = {5, 15, 91};// en binaire : 101 , 1111, 1011011   cout << First_bit(0) << endl;//output : 0 cout << First_bit(1) << endl;//output : 2 cout << First_bit(2) << endl;//output : 7   cout << Count_bit(0) << endl;// output : 2 cout << Count_bit(1) << endl;// output : 4 cout << Count_bit(2) << endl;// output : 5   return 0; } unsigned int GetFirstBitAt1 (unsigned int x) { unsigned int temp; __asm{ bsf eax,x; jz zero; jmp end; zero: xor eax,eax; end: mov temp, eax; } return temp; } unsigned int CountBitAt1 (unsigned int x) { unsigned int temp; _asm{ xor ecx,ecx;//compteur de boucle xor edx,edx;//compteur de bits movzx eax,x; boucle: bt eax,ecx; jnc nothing; inc edx; nothing: inc ecx; cmp ecx,16; //nombre de bits pour un UCHAR (de 0 à 15) jb boucle; mov temp,edx; } return temp; }

---

J'espère que ca t'ira :)

N'hésite pas si tu as des questions ou des remarques.

Salut !

Merci pour ces deux fonctions.
Helas les performances sont decevantes comparees a celles des 2 look-up tables.

L'instruction bsf consomme tellement de cycles que sur mon pentium 4 la lecture dans la table est (legerement) plus rapide.

Pour ce qui est du comptage des bits je viens de trouver l'algo suivant dans le "Software Optimization Guide for the AMD64 processors" (dispo sur le site d'AMD et vraiment de qualite) (et dire que sur les procs cray ou sparc il y a une instruction pour le comptage des bits ...).

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

_inline unsigned int popcount(unsigned int v) { unsigned int retVal;   __asm { mov eax, [v] ; v mov edx, eax ; v shr eax, 1 ; v >> 1 and eax, 055555555h ; (v >> 1) & 0x55555555 sub edx, eax ; w = v - ((v >> 1) & 0x55555555) mov eax, edx ; w shr edx, 2 ; w >> 2 and eax, 033333333h ; w & 0x33333333 and edx, 033333333h ; (w >> 2) & 0x33333333 add eax, edx ; x = (w & 0x33333333) + ((w >> 2) & 0x33333333) mov edx, eax ; x shr eax, 4 ; x >> 4 add eax, edx ; x + (x >> 4) and eax, 00F0F0F0Fh ; y = (x + (x >> 4) & 0x0F0F0F0F) imul eax, 001010101h ; y * 0x01010101 shr eax, 24 ; population count = (y * 0x01010101) >> 24 mov retVal, eax ; Store result. }   return(retVal); }

---

C'est cependant 2 ou 3 fois plus lent que ma look-up table.
Mais je ne m'interesse qu'aux 16 premiers bits alors que l'algo "AMD" marche pour un unsigned de 32 bits.

Bref sur ce coup je suis decu, j'esperai pouvoir gagner de la vitesse sur ces 2 fonctions et ca ne semble pas possible.

Une derniere pensee : peut etre que pour un algo qui brasse beaucoup de memoire le fait de recharger tout le temps les look-up tables devient handicapant, et dans ce cas peut-etre que bsf et le code AMD se mettent a valoir le coup ...