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

Подсчет количества бит - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 5.00
nsuperman
0 / 0 / 0
Регистрация: 13.06.2011
Сообщений: 4
02.11.2011, 01:47     Подсчет количества бит #1
Здравствуйте!
У меня есть функция, которая считает количество бит в 32-х разрядном
числе типа uint

#define g21 0x55555555ul // = 0101_0101_0101_0101_0101_0101_0101_0101
#define g22 0x33333333ul // = 0011_0011_0011_0011_0011_0011_0011_0011
#define g23 0x0f0f0f0ful // = 0000_1111_0000_1111_0000_1111_0000_1111

v = (v & g21) + ((v >> 1) & g21);
v = (v & g22) + ((v >> 2) & g22);
v = (v + (v >> 4)) & g23;
return (v + (v >> 8) + (v >> 16) + (v >> 24)) & 0x3f;

Но мне нужно переделать её так, чтобы она работала на int64 .
Пожалуйста, подскажите как это возможно сделать? Разбивать число на 2
части не очень хотелось бы, чтобы не испортить быстродействие.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.11.2011, 01:47     Подсчет количества бит
Посмотрите здесь:

подсчет количества нечетных чисел C++
C++ Подсчет количества символов
Подсчет количества слов C++
Подсчет количества слов C++
C++ Подсчет количества символов
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Евгений М.
1033 / 974 / 53
Регистрация: 28.02.2010
Сообщений: 2,817
Завершенные тесты: 2
02.11.2011, 04:29     Подсчет количества бит #2
Цитата Сообщение от nsuperman Посмотреть сообщение
У меня есть функция, которая считает количество бит в 32-х разрядном
числе типа uint
Количество бит в n-х разрядном числе разве не равен n?
nsuperman
0 / 0 / 0
Регистрация: 13.06.2011
Сообщений: 4
02.11.2011, 20:36  [ТС]     Подсчет количества бит #3
Ой, я имею в виду, конечно, количества единиц, т.е. бит, равных единице.
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
03.11.2011, 10:27     Подсчет количества бит #4
Но мне нужно переделать её так, чтобы она работала на int64
Ну если ты понимаешь как работает ЭТА функция,
то это как бы очевидно как переделать

Разбивать число на 2
части не очень хотелось бы, чтобы не испортить быстродействие.
Ну как бы очевидно что на 64 разряда будет медленнее
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
03.11.2011, 10:31     Подсчет количества бит #5
Цитата Сообщение от nsuperman Посмотреть сообщение
У меня есть функция, которая считает количество бит в 32-х разрядном
А зачем их считать? Их всегда 32, это известно априорно.
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
03.11.2011, 10:32     Подсчет количества бит #6
Не знаю будет быстрее или нет, можно попробовать такой способ

int count256[256];

// count256[i] = число битов в числе i

Тогда ответ будет очевиден

unsigned v;
int count= count256[ (v)&0x000000FF ]
+count256[ (v>>8)&0x000000FF ]+
+count256[ (v>>16)&0x000000FF ]+
+count256[ (v>>24)&0x000000FF ];

// count - число единичных бит

Добавлено через 39 секунд
Как бы очевидно как посчитать для
uint64_t v2;
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
03.11.2011, 10:40     Подсчет количества бит #7
C++
1
2
3
4
5
6
7
8
9
10
11
12
unsigned int count (unsigned int x) // аргумент может быть объявлен любым ансигнед интом, хоть однобайтным, хоть восьмибайтным, хоть в будующем ещё длинее, лишь бы встроенным
{
 int r;
 for (r=0; x!=0; x/=2)
 {
  if ((x%2)!=0)
  {
   ++r;
  }
 }
 return r;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.05.2014, 14:46     Подсчет количества бит
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Kant
 Аватар для Kant
24 / 24 / 8
Регистрация: 15.05.2013
Сообщений: 213
24.05.2014, 14:46     Подсчет количества бит #8
Не правильно.
C++
1
2
3
4
5
6
7
8
int GetCountBitOfInteger(unsigned int value) {
    int count_bit = 0;
    for(count_bit=0; value!=0; value/=2)
        if (value%2 == 0)
            ++count_bit;
 
    return ++count_bit;
}
Нахождение номера старшего бита числа
Добавлено через 34 минуты
http://cppalgo.blogspot.com/2012/06/blog-post.html

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int GetCountBitOfInteger(int n) {
    if(n == 0) return 1;
 
    const int MASK_R[6] = {0x0000FFFF, 0x000000FF, 0x0000000F, 0x00000003, 0x00000001};
 
    int size = sizeof(n)*4;
    int res = 0, m = 0, l = 0;
 
    while (n != 1) {
         l = n >> size;
        if (l) {
            n = l;
            res += size;
        }
        else n &= MASK_R[m];
 
        size >>= 1;
        m++;
    }
 
    return ++res;
}
Yandex
Объявления
24.05.2014, 14:46     Подсчет количества бит
Ответ Создать тему
Опции темы

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