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

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

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

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

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

Подсчет количества бит - 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++
написать программу какая с позиционной системы счисления выводит как число в десятичной системе счисления. То есть когда вводишь символы...

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryS
Модератор
6550 / 5016 / 463
Регистрация: 14.02.2011
Сообщений: 16,728
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++
Есть два файла, 1.txt и 2.txt Задание: 1) Скопировать в файл 2.txt только те строки из 1.txt, которые начинаются с буквы &quot;а&quot; ...

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

Подсчет количества уникальных слов - C++
Добрый день. Есть программа для подсчета количества слов тексте: #include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;string&gt; #include...

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


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

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

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