Форум программистов, компьютерный форум 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 );
}
Все работает, но очень уж меделено для моей задачи . Может, кто-то сталкивался с подобным, и есть идеи по увеличению скорости, или тут предел?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,040
28.11.2013, 09:13     Быстрый подсчет количества бит #21
Цитата Сообщение от stlex Посмотреть сообщение
Вот окончательный вариант моего класса.
итак
все началось с подсчета, а закончилось целым классом

Цитата Сообщение от stlex Посмотреть сообщение
C++
1
2
3
4
5
6
7
inline bool GetBit( int n )
{
 if( ( 1 << ( n % BITS_COUNT_INT ) ) & myMap[ n / BITS_COUNT_INT ] )
   return true;
    else
  return false;
}
на хрена тебе здесь ветвление ???тормозить будет
тем более явная тавтология
если 1 << ( n % BITS_COUNT_INT ) ) & myMap[ n / BITS_COUNT_INT ] ИСТИНА, то вернуть ИСТИНА
C++
1
2
3
4
inline bool GetBit( int n )
{
  return ( 1 << ( n % BITS_COUNT_INT ) ) & myMap[ n / BITS_COUNT_INT ] )!=0;
}
Цитата Сообщение от stlex Посмотреть сообщение
вот что значит оптимизация компилятора! Думаю, тут только на asm можно что-то существенно оптимизировать.
Не факт
для этого надо очень хорошо знать современные процессоры
распараллеливание команд, организация кэша, выравнивание.....
если посмотришь на код оптимизированной программы то увидишь кучу бесполезных команд типа
mov edx,edx
или замена деления умножением
по коду больше а выполняется быстрее
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
stlex
0 / 0 / 0
Регистрация: 27.11.2013
Сообщений: 8
28.11.2013, 10:07  [ТС]     Быстрый подсчет количества бит #22
Цитата Сообщение от ValeryS Посмотреть сообщение
на хрена тебе здесь ветвление ???тормозить будет
тем более явная тавтология
если 1 << ( n % BITS_COUNT_INT ) ) & myMap[ n / BITS_COUNT_INT ] ИСТИНА, то вернуть ИСТИНА
C++
1
2
3
4
inline bool GetBit( int n )
{
  return ( 1 << ( n % BITS_COUNT_INT ) ) & myMap[ n / BITS_COUNT_INT ] )!=0;
}
Согласен, спасбио.

C++
1
2
3
4
5
6
7
8
9
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;
   }
Тут косяк - всесто 11 нужно, самом собой, N
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.11.2013, 11:20     Быстрый подсчет количества бит
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 319
Регистрация: 30.03.2009
Сообщений: 14,121
Записей в блоге: 26
28.11.2013, 11:20     Быстрый подсчет количества бит #23
Цитата Сообщение от ValeryS Посмотреть сообщение
все началось с подсчета, а закончилось целым классом
Какой язык лучше учить?
Yandex
Объявления
28.11.2013, 11:20     Быстрый подсчет количества бит
Ответ Создать тему
Опции темы

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