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

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

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

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

27.11.2013, 10:08. Просмотров 1401. Ответов 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++
С клавиатуры вводится строка. Составить программу, которая подсчитывает количество слов, имеющих нечетную длину; вводит на экран частоту...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
CheshireCat
Эксперт С++
2892 / 1241 / 78
Регистрация: 27.05.2008
Сообщений: 3,370
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
Модератор
6631 / 5038 / 466
Регистрация: 14.02.2011
Сообщений: 16,849
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 / 0
Регистрация: 27.11.2013
Сообщений: 8
27.11.2013, 15:19  [ТС] #4
CheshireCat , это реально круто
Спасибо!

Добавлено через 1 минуту
А зачем????
причем здесь массив?
вот простой цикл
Способ хороший, но немного медленнее
0
ValeryS
Модератор
6631 / 5038 / 466
Регистрация: 14.02.2011
Сообщений: 16,849
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 / 0
Регистрация: 27.11.2013
Сообщений: 8
27.11.2013, 16:00  [ТС] #6
ValeryS, Все верно, но в моей задаче число единиц и нулей ожидаются примерно равными, и итераций будет близко к тридцати. При измерении быстродействия на реальных данных способ с массивами самым быстрым оказался
0
ValeryS
Модератор
6631 / 5038 / 466
Регистрация: 14.02.2011
Сообщений: 16,849
27.11.2013, 16:06 #7
Цитата Сообщение от stlex Посмотреть сообщение
При измерении быстродействия на реальных данных способ с массивами самым быстрым оказался
а где ты у CheshireCat, увидел массивы ?
там используются битовые маски
не спорю для реальных данных способ быстрей
но не такой очевидный
0
stlex
0 / 0 / 0
Регистрация: 27.11.2013
Сообщений: 8
27.11.2013, 16:22  [ТС] #8
Цитата Сообщение от ValeryS Посмотреть сообщение
а где ты у CheshireCat, увидел массивы ?
там используются битовые маски
не спорю для реальных данных способ быстрей
но не такой очевидный
Я про свой способ говорю, который в заглавном посте. Он самый быстрый
0
ValeryS
Модератор
6631 / 5038 / 466
Регистрация: 14.02.2011
Сообщений: 16,849
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 / 0
Регистрация: 27.11.2013
Сообщений: 8
27.11.2013, 16:56  [ТС] #10
честно говоря я так и не понял твой способ он вроде табличный
но каждый раз вызывается вот это
InitMas( mas );
Неа, только один раз, при инициализации static переменной
C++
1
static bool init = InitMas( mas );
0
ValeryS
Модератор
6631 / 5038 / 466
Регистрация: 14.02.2011
Сообщений: 16,849
27.11.2013, 17:09 #11
Цитата Сообщение от stlex Посмотреть сообщение
Неа, только один раз, при инициализации static переменной
тогда что у тебя тормозит?
Цитата Сообщение от stlex Посмотреть сообщение
Все работает, но очень уж меделено для моей задачи
может первый вызов?
так инициализируй массив сразу как запустил программу, до всех расчетов
0
CheshireCat
Эксперт С++
2892 / 1241 / 78
Регистрация: 27.05.2008
Сообщений: 3,370
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
17810 / 6016 / 388
Регистрация: 30.03.2009
Сообщений: 16,531
Записей в блоге: 26
27.11.2013, 18:23 #13
Не забывайте, что массив для 0x0000 - 0xFFFF (т.е. в нём 65536 элементов)

На пример из поста #12 в теории могут сказать, что он ednian-зависимый (если преподаватель вообще знает, что это такое). На это можно ответить, что от перестановки порядка байт количество единиц в них не поменяется
0
ValeryS
Модератор
6631 / 5038 / 466
Регистрация: 14.02.2011
Сообщений: 16,849
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
17810 / 6016 / 388
Регистрация: 30.03.2009
Сообщений: 16,531
Записей в блоге: 26
27.11.2013, 18:43 #15
Цитата Сообщение от ValeryS Посмотреть сообщение
единственно что меня терзают смутные сомнения, можно ли такой массив выделять статически
Можно. Это всего 64 килобайта - мелочь даже по меркам DOS'а
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.11.2013, 18:43
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
27.11.2013, 18:43
Ответ Создать тему
Опции темы

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