Форум программистов, компьютерный форум CyberForum.ru

Быстрый подсчет количества бит - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
stlex
0 / 0 / 0
Регистрация: 27.11.2013
Сообщений: 8
27.11.2013, 10:08     Быстрый подсчет количества бит #1
Нужно подсчитать количество бит, равных единице в int32, использую статический массив, в котором заранее подсчитаны значения для 0x0000 - 0xFFFF

C++
1
2
3
4
5
6
7
8
9
10
11
12
inline unsigned __int8 BitCount16( unsigned __int16 k )
{
   static unsigned __int8 mas[0x10000];
   static bool init = InitMas( mas );
   return mas[ k ];
}
 
template<>
inline unsigned __int8 BitCountImpl<__int32>( int *k )
{
   return BitCount16( *k >> 16 ) + BitCount16( *k & 0xFFFF );
}
Все работает, но очень уж меделено для моей задачи . Может, кто-то сталкивался с подобным, и есть идеи по увеличению скорости, или тут предел?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
CheshireCat
Эксперт С++
2907 / 1235 / 78
Регистрация: 27.05.2008
Сообщений: 3,309
27.11.2013, 13:17     Быстрый подсчет количества бит #2
C++
1
2
3
4
5
6
7
8
9
uint8_t num_of_bits32(uint32_t _arg)
{
    _arg = (_arg & 0x55555555L) + ((_arg >> 1) & 0x55555555L);
    _arg = (_arg & 0x33333333L) + ((_arg >> 2) & 0x33333333L);
    _arg = (_arg + (_arg >> 4)) & 0x0F0F0F0FL;
    _arg = _arg + (_arg >> 8);
 
    return (uint8_t)(_arg + (_arg >> 16)) & 0x3F;
}
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
27.11.2013, 13:51     Быстрый подсчет количества бит #3
Цитата Сообщение от stlex Посмотреть сообщение
Нужно подсчитать количество бит, равных единице в int32, использую статический массив,
А зачем????
причем здесь массив?
вот простой цикл
C++
1
2
3
4
5
6
7
8
9
10
int fncSumm(unsigned int n)
{
int summ=0;
for(int i=0;i<sizeof(int)*8;i++)
{
int k=(n>>i)&0x01;
summ+=k;
}
return summ;
}
stlex
0 / 0 / 0
Регистрация: 27.11.2013
Сообщений: 8
27.11.2013, 15:19  [ТС]     Быстрый подсчет количества бит #4
CheshireCat , это реально круто
Спасибо!

Добавлено через 1 минуту
А зачем????
причем здесь массив?
вот простой цикл
Способ хороший, но немного медленнее
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
27.11.2013, 15:50     Быстрый подсчет количества бит #5
Цитата Сообщение от stlex Посмотреть сообщение
Способ хороший, но немного медленнее
32 итерации цикла это медленно?
может быть зато все на виду
ну вот побыстрее
C++
1
2
3
4
5
6
7
8
9
10
int fncSumm(unsigned int n)
{
int summ=0;
while(n)
{
summ+=n&0x01;
n/=2;
}
return summ;
}
максимум 32 итерации а
если число типа 1 то вообще 1 итерация если 0 то ни одной
stlex
0 / 0 / 0
Регистрация: 27.11.2013
Сообщений: 8
27.11.2013, 16:00  [ТС]     Быстрый подсчет количества бит #6
ValeryS, Все верно, но в моей задаче число единиц и нулей ожидаются примерно равными, и итераций будет близко к тридцати. При измерении быстродействия на реальных данных способ с массивами самым быстрым оказался
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
27.11.2013, 16:06     Быстрый подсчет количества бит #7
Цитата Сообщение от stlex Посмотреть сообщение
При измерении быстродействия на реальных данных способ с массивами самым быстрым оказался
а где ты у CheshireCat, увидел массивы ?
там используются битовые маски
не спорю для реальных данных способ быстрей
но не такой очевидный
stlex
0 / 0 / 0
Регистрация: 27.11.2013
Сообщений: 8
27.11.2013, 16:22  [ТС]     Быстрый подсчет количества бит #8
Цитата Сообщение от ValeryS Посмотреть сообщение
а где ты у CheshireCat, увидел массивы ?
там используются битовые маски
не спорю для реальных данных способ быстрей
но не такой очевидный
Я про свой способ говорю, который в заглавном посте. Он самый быстрый
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
27.11.2013, 16:49     Быстрый подсчет количества бит #9
Цитата Сообщение от stlex Посмотреть сообщение
Я про свой способ говорю, который в заглавном посте. Он самый быстрый
Цитата Сообщение от stlex Посмотреть сообщение
Все работает, но очень уж меделено для моей задачи
определись
ну могу показать табличный способ, он будет самый быстрый
правда памяти будет жрать
честно говоря я так и не понял твой способ он вроде табличный
но каждый раз вызывается вот это
Цитата Сообщение от stlex Посмотреть сообщение
InitMas( mas );
вот так нужно было делать
с массивом на 16 элементов массив забивается на этапе компиляции
C++
1
2
3
4
5
6
7
8
9
10
11
12
int arr[16]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
 
int fncSumm(unsigned int n)
{
int summ=0;
while(n)
{
summ+=arr[n&0x0F];
n/=16;
}
return summ;
}
тоже самое но таблица рассчитывается при запуске программы размер 256

C++
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
int arr[256];
void initArr()
{
  for(int i=0;i<256;i++)
   {
    int j=i;
    int summ=0;
    while(j)
    {
       summ+=n&jx01;
       j/=2;
    }
   arr[i]=summ;
  }
 
}
.........................
int fncSumm(unsigned int n)
{
int summ=0;
 while(n)
  {
   summ+=arr[n&0xFF];
   n/=256;
  }
 return summ;
}
тоже но размер таблицы больше лучше выделять динамически
C++
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
int * arr;
void initArr()
{
 arr=new[65536]
 for(int i=0;i<65536;i++)
   {
    int j=i;
    int summ=0;
    while(j)
    {
       summ+=n&jx01;
       j/=2;
    }
   arr[i]=summ;
  }
 
}
.........................
int fncSumm(unsigned int n)
{
int summ=0;
summ+=arr[n&0xFFFF];
summ+=arr[(n>>16)&0xFFFF];
 return summ;
}
как видишь чем больше размер массива(таблицы) тем шустрее вычисления
но расплата память
в идеале вообще таблица размером в 4294967296 самая быстрая но где столько памяти взять
stlex
0 / 0 / 0
Регистрация: 27.11.2013
Сообщений: 8
27.11.2013, 16:56  [ТС]     Быстрый подсчет количества бит #10
честно говоря я так и не понял твой способ он вроде табличный
но каждый раз вызывается вот это
InitMas( mas );
Неа, только один раз, при инициализации static переменной
C++
1
static bool init = InitMas( mas );
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
27.11.2013, 17:09     Быстрый подсчет количества бит #11
Цитата Сообщение от stlex Посмотреть сообщение
Неа, только один раз, при инициализации static переменной
тогда что у тебя тормозит?
Цитата Сообщение от stlex Посмотреть сообщение
Все работает, но очень уж меделено для моей задачи
может первый вызов?
так инициализируй массив сразу как запустил программу, до всех расчетов
CheshireCat
Эксперт С++
2907 / 1235 / 78
Регистрация: 27.05.2008
Сообщений: 3,309
27.11.2013, 17:51     Быстрый подсчет количества бит #12
Ну можно еще попытаться замутить что-нибудь вида
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
// предвычисленная в compile-time таблица числа единичных битов в байте
_int8 numBits[256] = { 0, 1, 1, 2, 1... };
 
template<>
inline unsigned __int8 BitCountImpl<__int32>( int *k )
{
   union {
      _int8 b0, b1, b2, b3;
      int a;
   } x;
   x.a = *k;
   return numBits[x.b0] + numBits[x.b1] + numBits[x.b2] + numBits[x.b3];
}
Вообще, использование предвычисленных таблиц - это самый быстрый способ.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16843 / 5264 / 323
Регистрация: 30.03.2009
Сообщений: 14,159
Записей в блоге: 26
27.11.2013, 18:23     Быстрый подсчет количества бит #13
Не забывайте, что массив для 0x0000 - 0xFFFF (т.е. в нём 65536 элементов)

На пример из поста #12 в теории могут сказать, что он ednian-зависимый (если преподаватель вообще знает, что это такое). На это можно ответить, что от перестановки порядка байт количество единиц в них не поменяется
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
27.11.2013, 18:39     Быстрый подсчет количества бит #14
Цитата Сообщение от Evg Посмотреть сообщение
Не забывайте, что массив для 0x0000 - 0xFFFF (т.е. в нём 65536 элементов)
так вроде никто и не забывал
у меня
Цитата Сообщение от ValeryS Посмотреть сообщение
arr=new[65536]
у ТС
Цитата Сообщение от stlex Посмотреть сообщение
mas[0x10000];
единственно что меня терзают смутные сомнения, можно ли такой массив выделять статически
он хоть и в глобальной области
Цитата Сообщение от stlex Посмотреть сообщение
static
но уж больно большой, запустится ли?

Добавлено через 1 минуту
Цитата Сообщение от Evg Посмотреть сообщение
На это можно ответить, что от перестановки порядка байт количество единиц в них не поменяется
даже если поменять порядок бит, тоже не поменяется
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16843 / 5264 / 323
Регистрация: 30.03.2009
Сообщений: 14,159
Записей в блоге: 26
27.11.2013, 18:43     Быстрый подсчет количества бит #15
Цитата Сообщение от ValeryS Посмотреть сообщение
единственно что меня терзают смутные сомнения, можно ли такой массив выделять статически
Можно. Это всего 64 килобайта - мелочь даже по меркам DOS'а
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
27.11.2013, 18:46     Быстрый подсчет количества бит #16
Цитата Сообщение от Evg Посмотреть сообщение
Это всего 64 килобайта - мелочь даже по меркам DOS'а
насколько помню это размер сегмента
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16843 / 5264 / 323
Регистрация: 30.03.2009
Сообщений: 14,159
Записей в блоге: 26
27.11.2013, 18:48     Быстрый подсчет количества бит #17
В 16-битном режиме - да. Но оно ушло в прошлое лет 18 назад. Для современных компиляторов статических данных "много" - это когда исчисляется мегабайтами
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
27.11.2013, 18:53     Быстрый подсчет количества бит #18
Цитата Сообщение от Evg Посмотреть сообщение
В 16-битном режиме - да. Но оно ушло в прошлое лет 18 назад.
ну к ДОС тоже
Цитата Сообщение от Evg Посмотреть сообщение
Для современных компиляторов статических данных "много" - это когда исчисляется мегабайтами
опасаюсь я
как то нужно было выделить 512 скроллеров ( окна такие)
так прога рухнула не успев запустится
не помню статик объявлял или нет(давно было) т.е данные в стеке или в глобальной области
но с тех пор как то при больших размерах динамику предпочитаю
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16843 / 5264 / 323
Регистрация: 30.03.2009
Сообщений: 14,159
Записей в блоге: 26
27.11.2013, 19:00     Быстрый подсчет количества бит #19
Не сцы, от 64 килобайт точно не рухнет
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.11.2013, 08:35     Быстрый подсчет количества бит
Еще ссылки по теме:

C++ Подсчет количества символов
C++ Подсчет количества слов
Быстрый подсчет чисел, подходящих под условие C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
stlex
0 / 0 / 0
Регистрация: 27.11.2013
Сообщений: 8
28.11.2013, 08:35  [ТС]     Быстрый подсчет количества бит #20
Вот окончательный вариант моего класса. Убрал лишние вложенные вызовы функций, и теперь BitCount() приблизился по скорости к &= , SetBit() и прочим. А быстрее всего работает автогенерированный operator=() - вот что значит оптимизация компилятора! Думаю, тут только на asm можно что-то существенно оптимизировать.
Может, код пригодится кому-то.
C++
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
60
61
62
63
64
65
template<int N>
class BitMap
{   
public:
   BitMap()
   {
      Clear();
   }
   inline void Clear()
   {
      ZeroMemory( myMap, N * sizeof(__int32) );
   }
   inline bool GetBit( int n )
   {
      if( ( 1 << ( n % BITS_COUNT_INT ) ) & myMap[ n / BITS_COUNT_INT ] )
         return true;
      else
         return false;
   }
   inline void SetBit( int n )
   {
      myMap[ n / BITS_COUNT_INT ] |=  1 << ( n % BITS_COUNT_INT );
   }
   inline void ClearBit( int n )
   {
      myMap[ n / BITS_COUNT_INT ] &= ~( 1 << ( n % BITS_COUNT_INT ) );
   }
   int BitCount()
   {
      static unsigned __int8 mas[0x10000];
      static bool init = InitMas( mas );
      int res = 0;
      for( int i = 0; i < 11; ++i )
         res += mas[ (unsigned __int16)(myMap[i] >> 16) ] + mas[ (unsigned __int16)(myMap[i] & 0xFFFF) ];
      return res;
   }
   BitMap<N>& operator&=( const BitMap<N>& other )
   {
      for( int i = 0; i < N; ++i )
         myMap[i] &= other.myMap[i];
      return *this;
   }
   BitMap<N>& operator|=( const BitMap<N>& other )
   {
      for( int i = 0; i < N; ++i )
         myMap[i] |= other.myMap[i];
      return *this;
   }
private:
   static bool InitMas( unsigned __int8 *mas )
   {
      for( int i = 0; i < 0x10000; ++i )
      {
         unsigned __int8 count = 0;
         for( int tmp = i; tmp > 0; tmp = tmp / 2 )
         {
            if( tmp % 2 )
               ++count;
         }
         mas[i] = count;
      }
      return true;
   }
   __int32 myMap[N];
};
Yandex
Объявления
28.11.2013, 08:35     Быстрый подсчет количества бит
Ответ Создать тему
Опции темы

Текущее время: 05:18. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru