Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 5.00/9: Рейтинг темы: голосов - 9, средняя оценка - 5.00
stlex
0 / 0 / 1
Регистрация: 27.11.2013
Сообщений: 8
1

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

27.11.2013, 10:08. Просмотров 1614. Ответов 22
Метки нет (Все метки)

Нужно подсчитать количество бит, равных единице в 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 );
}
Все работает, но очень уж меделено для моей задачи . Может, кто-то сталкивался с подобным, и есть идеи по увеличению скорости, или тут предел?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.11.2013, 10:08
Ответы с готовыми решениями:

Быстрый подсчёт количества выставленных бит после битовой операции
Допустим есть два числа, выглядящие в бинарном виде так: 1. 00101011 2....

Подсчет количества бит
Здравствуйте! У меня есть функция, которая считает количество бит в 32-х...

Быстрый подсчет чисел, подходящих под условие
Нужно на отрезке найти кол-во чисел удовлетворяющих условию (N 2 − 1) mod K =...

Подскажите быстрый поиск количества интервалов в отрезке
Есть массив H Есть отрезок x+dx. Задача найти количество интервалов на...

Быстрый алгоритм для подсчета количества делителей числа
Быстрый алгоритм для подсчета количества делителей натурального числа 1 &lt;= x &lt;=...

22
CheshireCat
Эксперт С++
2912 / 1261 / 114
Регистрация: 27.05.2008
Сообщений: 3,464
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;
}
1
ValeryS
Модератор
7264 / 5518 / 692
Регистрация: 14.02.2011
Сообщений: 18,691
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;
}
0
stlex
0 / 0 / 1
Регистрация: 27.11.2013
Сообщений: 8
27.11.2013, 15:19  [ТС] 4
CheshireCat , это реально круто
Спасибо!

Добавлено через 1 минуту
А зачем????
причем здесь массив?
вот простой цикл
Способ хороший, но немного медленнее
0
ValeryS
Модератор
7264 / 5518 / 692
Регистрация: 14.02.2011
Сообщений: 18,691
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 то ни одной
1
stlex
0 / 0 / 1
Регистрация: 27.11.2013
Сообщений: 8
27.11.2013, 16:00  [ТС] 6
ValeryS, Все верно, но в моей задаче число единиц и нулей ожидаются примерно равными, и итераций будет близко к тридцати. При измерении быстродействия на реальных данных способ с массивами самым быстрым оказался
0
ValeryS
Модератор
7264 / 5518 / 692
Регистрация: 14.02.2011
Сообщений: 18,691
27.11.2013, 16:06 7
Цитата Сообщение от stlex Посмотреть сообщение
При измерении быстродействия на реальных данных способ с массивами самым быстрым оказался
а где ты у CheshireCat, увидел массивы ?
там используются битовые маски
не спорю для реальных данных способ быстрей
но не такой очевидный
0
stlex
0 / 0 / 1
Регистрация: 27.11.2013
Сообщений: 8
27.11.2013, 16:22  [ТС] 8
Цитата Сообщение от ValeryS Посмотреть сообщение
а где ты у CheshireCat, увидел массивы ?
там используются битовые маски
не спорю для реальных данных способ быстрей
но не такой очевидный
Я про свой способ говорю, который в заглавном посте. Он самый быстрый
0
ValeryS
Модератор
7264 / 5518 / 692
Регистрация: 14.02.2011
Сообщений: 18,691
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 самая быстрая но где столько памяти взять
1
stlex
0 / 0 / 1
Регистрация: 27.11.2013
Сообщений: 8
27.11.2013, 16:56  [ТС] 10
честно говоря я так и не понял твой способ он вроде табличный
но каждый раз вызывается вот это
InitMas( mas );
Неа, только один раз, при инициализации static переменной
C++
1
static bool init = InitMas( mas );
0
ValeryS
Модератор
7264 / 5518 / 692
Регистрация: 14.02.2011
Сообщений: 18,691
27.11.2013, 17:09 11
Цитата Сообщение от stlex Посмотреть сообщение
Неа, только один раз, при инициализации static переменной
тогда что у тебя тормозит?
Цитата Сообщение от stlex Посмотреть сообщение
Все работает, но очень уж меделено для моей задачи
может первый вызов?
так инициализируй массив сразу как запустил программу, до всех расчетов
0
CheshireCat
Эксперт С++
2912 / 1261 / 114
Регистрация: 27.05.2008
Сообщений: 3,464
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];
}
Вообще, использование предвычисленных таблиц - это самый быстрый способ.
0
Evg
Эксперт CАвтор FAQ
19288 / 7147 / 528
Регистрация: 30.03.2009
Сообщений: 19,997
Записей в блоге: 30
27.11.2013, 18:23 13
Не забывайте, что массив для 0x0000 - 0xFFFF (т.е. в нём 65536 элементов)

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

Добавлено через 1 минуту
Цитата Сообщение от Evg Посмотреть сообщение
На это можно ответить, что от перестановки порядка байт количество единиц в них не поменяется
даже если поменять порядок бит, тоже не поменяется
0
Evg
Эксперт CАвтор FAQ
19288 / 7147 / 528
Регистрация: 30.03.2009
Сообщений: 19,997
Записей в блоге: 30
27.11.2013, 18:43 15
Цитата Сообщение от ValeryS Посмотреть сообщение
единственно что меня терзают смутные сомнения, можно ли такой массив выделять статически
Можно. Это всего 64 килобайта - мелочь даже по меркам DOS'а
0
ValeryS
Модератор
7264 / 5518 / 692
Регистрация: 14.02.2011
Сообщений: 18,691
27.11.2013, 18:46 16
Цитата Сообщение от Evg Посмотреть сообщение
Это всего 64 килобайта - мелочь даже по меркам DOS'а
насколько помню это размер сегмента
0
Evg
Эксперт CАвтор FAQ
19288 / 7147 / 528
Регистрация: 30.03.2009
Сообщений: 19,997
Записей в блоге: 30
27.11.2013, 18:48 17
В 16-битном режиме - да. Но оно ушло в прошлое лет 18 назад. Для современных компиляторов статических данных "много" - это когда исчисляется мегабайтами
0
ValeryS
Модератор
7264 / 5518 / 692
Регистрация: 14.02.2011
Сообщений: 18,691
27.11.2013, 18:53 18
Цитата Сообщение от Evg Посмотреть сообщение
В 16-битном режиме - да. Но оно ушло в прошлое лет 18 назад.
ну к ДОС тоже
Цитата Сообщение от Evg Посмотреть сообщение
Для современных компиляторов статических данных "много" - это когда исчисляется мегабайтами
опасаюсь я
как то нужно было выделить 512 скроллеров ( окна такие)
так прога рухнула не успев запустится
не помню статик объявлял или нет(давно было) т.е данные в стеке или в глобальной области
но с тех пор как то при больших размерах динамику предпочитаю
0
Evg
Эксперт CАвтор FAQ
19288 / 7147 / 528
Регистрация: 30.03.2009
Сообщений: 19,997
Записей в блоге: 30
27.11.2013, 19:00 19
Не сцы, от 64 килобайт точно не рухнет
0
stlex
0 / 0 / 1
Регистрация: 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];
};
0
28.11.2013, 08:35
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.11.2013, 08:35

Быстрый подсчет A^B mod C или "Алгоритм русского крестьянина"
Нужно максимально быстро посчитать A^B mod C. Написала алгоритм, казалось бы...

Подсчет количества слов
Есть два файла, 1.txt и 2.txt Задание: 1) Скопировать в файл 2.txt...

Подсчет количества слов
Допустим, дана строка: &quot;129 s23 ertr 234 0 e&quot; Как подсчитать количество...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru