Ivo Bloechliger wrote:
>
>>On Thu, Aug 29, 2002 at 06:34:28PM +0200, Francois Ryser wrote:
>>
>>>Bonjours,
>>>
>>>Je recherche une methode en c++ de compter le nombre de bits a 1 dans des
>>>mots de 16 bits, mais avec un imperatif de vitesse car nous devons faire sur
>>>1 million de mots de 16 bits
>>>
> Je pense que l'utilisation d'op�rations sur bits devrait �tre plus
> rapide du style (pour l'int�rieur de la boucle).
>
> r += w & 1; // bit-wise logical AND
> w >>=1; // bit-shift
unsigned int while_cnt (unsigned int mot)
{
unsigned int res = 0;
while (mot != 0) {
res += mot & 1;
mot >>= 1;
}
return res;
}
Ou bien le plus simple, avec la biblioth�que standard :
unsigned int std_cnt (unsigned short mot)
{
return std::bitset<16>(mot).count();
}
> Sinon faire un tableau � 65536 (=2^16) entr�es et stocker les r�sultat
> peut valoir la peine dans ton cas �galement.
unsigned int tab_cnt2 (unsigned short mot)
{
return lookup16[mot];
}
Ou bien avec un tableau de 256 entr�es utilis� 2 fois.
unsigned int tab_cnt (unsigned short mot)
{
return lookup8[mot & 0xFF] + lookup8[mot >> 8];
}
> Mais bon il y a encore mieux :-(
> http://www.devx.com/free/tips/tipview.asp?content_id=3839
Certainement la plus rapide pour des mots de 32 bits.
On pourrait sans doute l'optimiser pour du 16 bits
car j'obtiens de meilleures r�sultat avec double lookup
(sans doute meilleur que lookup2 car utilisant mieux la
cache de donn�es).
Temps relatifs sur mon PC (K6)
0.162030 s par tab_cnt
0.200805 s par count_bits
0.239354 s par tab_cnt2
0.343694 s par std_cnt
0.445795 s par while_cnt
Marc Mongenet
--
http://www-internal.alphanet.ch/linux-leman/ avant de poser
une question. Ouais, pour se d�sabonner aussi.
