Сканирование бит

Booster
Угу, с таблицей на 256 байт слишком много операций получается, а вот с таблицей на 65536 по скорости почти сравнимо с кодом из 56 сообщения.

 

murder
Спасибо всего за 14.5 тактов выполняется на Атлон ХР 2200 (1.81 ГГц), правда для 32 битных.

 

Шутишь?

Код (Text):

1. #include <iostream>
2. #include <algorithm>
3.  
4. unsigned int popcount(unsigned int v);
5. unsigned int bitcount(unsigned int n);
6. int bits_in_16bits[0x10000];
7. int test1(int a[], int size);
8. int test2(int a[], int size);
9. unsigned int bitcountFast (unsigned int n);
10.  
11. int main (int argc, char* argv[])
12. {
13.     for (int i=0; i<0x10000; i++)
14.     {
15.         bits_in_16bits[i] = bitcount(i);
16.     }
17.     int n = 0x100000;
18.     int array[n];
19.     for (int i=0; i<n; i++)
20.     {
21.         array[i] = std::rand();
22.     }
23.     int res2 = test2(array, n);
24.     int res1 = test1(array, n);
25.     std::cout<<res1<<" "<<res2<<std::endl;
26. }
27.  
28. int test1(int a[], int size)
29. {
30.     int res = 0;
31.     for (int c=0; c<100; c++)
32.     {
33.         for (int i=0; i<size; i++)
34.         {
35.             res += popcount(a[i]);
36.         }
37.     }
38.     return res;
39. }
40.  
41. int test2(int a[], int size)
42. {
43.         int res = 0;
44.     for (int c=0; c<100; c++)
45.     {
46.             for (int i=0; i<size; i++)
47.             {
48.                     res += bitcountFast(a[i]);
49.             }
50.     }
51.         return res;
52. }
53.  
54. unsigned int popcount(unsigned int v)
55. {
56.         unsigned int retVal;
57.     __asm (
58.     ".intel_syntax noprefix\n"
59.     "MOV    EAX,%0      \n"
60.     "MOV    EDX,EAX     \n"
61.     "SHR    EAX,1       \n"
62.     "AND    EAX,0x055555555 \n"
63.     "SUB    EDX,EAX     \n"
64.     "MOV    EAX,EDX     \n"
65.     "SHR    EDX,2       \n"
66.     "AND    EAX,0x033333333 \n"
67.     "AND    EDX,0x033333333 \n"
68.     "ADD    EAX,EDX     \n"
69.     "MOV    EDX,EAX     \n"
70.     "SHR    EAX,4       \n"
71.     "ADD    EAX,EDX     \n"
72.     "AND    EAX,0x00F0F0F0F \n"
73.     "IMUL   EAX,0x001010101 \n"
74.     "SHR    EAX,24      \n"
75.     "MOV    %1,EAX"
76.     :"=r"(retVal)
77.     :"r"(v)
78.     );
79.     return retVal;
80. }
81.  
82. unsigned int bitcount(unsigned int n)
83. {
84.    /* works for 32-bit numbers only    */
85.    /* fix last line for 64-bit numbers */
86.  
87.    register unsigned int tmp;
88.  
89.    tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
90.    return ((tmp + (tmp >> 3)) & 030707070707) % 63;
91. }
92.  
93. unsigned int bitcountFast (unsigned int n)  {
94.    // works only for 32-bit ints
95.    //
96.    return bits_in_16bits [n & 0xffff] +  bits_in_16bits [(n >> 16) & 0xffff] ;
97. }

Код (Text):

1. Flat profile:                                                
2.  
3. Each sample counts as 0.01 seconds.
4.   %   cumulative   self              self     total          
5.  time   seconds   seconds    calls   s/call   s/call  name    
6.  48.10      2.14     2.14 104857600     0.00     0.00  popcount(unsigned int)
7.  28.61      3.41     1.27 104857600     0.00     0.00  bitcountFast(unsigned int)