Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
stlex
0 / 0 / 0
Регистрация: 27.11.2013
Сообщений: 8
#1

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

27.11.2013, 10:08. Просмотров 1448. Ответов 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
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Быстрый подсчет количества бит (C++):

Подсчет количества бит - C++
Здравствуйте! У меня есть функция, которая считает количество бит в 32-х разрядном числе типа uint #define g21...

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

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

Быстрый алгоритм для подсчета количества делителей числа - C++
Быстрый алгоритм для подсчета количества делителей натурального числа 1 &lt;= x &lt;= 1018. Помогите реализовать такой. Дело в том, что должно...

Быстрый подсчет A^B mod C или "Алгоритм русского крестьянина" - C++
Нужно максимально быстро посчитать A^B mod C. Написала алгоритм, казалось бы все хорошо, да вот только сижу я на e-olimp'e, делаю задачки,...

Подсчет количества слов - C++
С клавиатуры вводится строка. Составить программу, которая подсчитывает количество слов, имеющих нечетную длину; вводит на экран частоту...

22
ValeryS
Модератор
6709 / 5118 / 482
Регистрация: 14.02.2011
Сообщений: 17,211
27.11.2013, 18:46 #16
Цитата Сообщение от Evg Посмотреть сообщение
Это всего 64 килобайта - мелочь даже по меркам DOS'а
насколько помню это размер сегмента
0
Evg
Эксперт CАвтор FAQ
18253 / 6378 / 438
Регистрация: 30.03.2009
Сообщений: 17,656
Записей в блоге: 28
27.11.2013, 18:48 #17
В 16-битном режиме - да. Но оно ушло в прошлое лет 18 назад. Для современных компиляторов статических данных "много" - это когда исчисляется мегабайтами
0
ValeryS
Модератор
6709 / 5118 / 482
Регистрация: 14.02.2011
Сообщений: 17,211
27.11.2013, 18:53 #18
Цитата Сообщение от Evg Посмотреть сообщение
В 16-битном режиме - да. Но оно ушло в прошлое лет 18 назад.
ну к ДОС тоже
Цитата Сообщение от Evg Посмотреть сообщение
Для современных компиляторов статических данных "много" - это когда исчисляется мегабайтами
опасаюсь я
как то нужно было выделить 512 скроллеров ( окна такие)
так прога рухнула не успев запустится
не помню статик объявлял или нет(давно было) т.е данные в стеке или в глобальной области
но с тех пор как то при больших размерах динамику предпочитаю
0
Evg
Эксперт CАвтор FAQ
18253 / 6378 / 438
Регистрация: 30.03.2009
Сообщений: 17,656
Записей в блоге: 28
27.11.2013, 19:00 #19
Не сцы, от 64 килобайт точно не рухнет
0
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];
};
0
ValeryS
Модератор
6709 / 5118 / 482
Регистрация: 14.02.2011
Сообщений: 17,211
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
или замена деления умножением
по коду больше а выполняется быстрее
1
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
0
Evg
Эксперт CАвтор FAQ
18253 / 6378 / 438
Регистрация: 30.03.2009
Сообщений: 17,656
Записей в блоге: 28
28.11.2013, 11:20 #23
Цитата Сообщение от ValeryS Посмотреть сообщение
все началось с подсчета, а закончилось целым классом
Какой язык лучше учить?
0
28.11.2013, 11:20
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.11.2013, 11:20
Привет! Вот еще темы с ответами:

Подсчет количества слов - C++
Допустим, дана строка: &quot;129 s23 ertr 234 0 e&quot; Как подсчитать количество слов, состоящих только из латинских букв?

Подсчет количества символов - C++
Доброго времени суток всем! помогите,пожалуйста,решить задачу: Программа должна подсчитывать количество символов в заданном текстовом...

Подсчет количества символов - C++
написать программу какая с позиционной системы счисления выводит как число в десятичной системе счисления. То есть когда вводишь символы...

Подсчет количества слов - C++
Есть два файла, 1.txt и 2.txt Задание: 1) Скопировать в файл 2.txt только те строки из 1.txt, которые начинаются с буквы &quot;а&quot; ...


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

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

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