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

Тема в разделе "WASM.A&O", создана пользователем persicum, 2 апр 2008.

  1. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Booster
    Угу, с таблицей на 256 байт слишком много операций получается, а вот с таблицей на 65536 по скорости почти сравнимо с кодом из 56 сообщения.
     
  2. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    561
    murder
    Спасибо всего за 14.5 тактов выполняется на Атлон ХР 2200 (1.81 ГГц), правда для 32 битных.
     
  3. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Шутишь?

    Код (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)