0 / 0 / 0
Регистрация: 13.06.2011
Сообщений: 4
1

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

02.11.2011, 01:47. Показов 4152. Ответов 7
Метки нет (Все метки)

Здравствуйте!
У меня есть функция, которая считает количество бит в 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
части не очень хотелось бы, чтобы не испортить быстродействие.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.11.2011, 01:47
Ответы с готовыми решениями:

Быстрый подсчет количества бит
Нужно подсчитать количество бит, равных единице в int32, использую статический массив, в котором...

Быстрый подсчёт количества выставленных бит после битовой операции
Допустим есть два числа, выглядящие в бинарном виде так: 1. 00101011 2. 10101000 делаю операцию...

Напечатать его в порядке возрастания количества бит установленных для a[i] в 0
Дан целый массив a, заполнить его по формуле a = 7*i+11, напечатать его в порядке возрастания...

Подсчёт количества подстрок
Посмотрите пожалуйста нормально ли написана функция, которая считает количество подстрок? int...

7
1080 / 1006 / 106
Регистрация: 28.02.2010
Сообщений: 2,889
02.11.2011, 04:29 2
Цитата Сообщение от nsuperman Посмотреть сообщение
У меня есть функция, которая считает количество бит в 32-х разрядном
числе типа uint
Количество бит в n-х разрядном числе разве не равен n?
0
0 / 0 / 0
Регистрация: 13.06.2011
Сообщений: 4
02.11.2011, 20:36  [ТС] 3
Ой, я имею в виду, конечно, количества единиц, т.е. бит, равных единице.
0
Эксперт С++
7175 / 3234 / 80
Регистрация: 17.06.2009
Сообщений: 14,164
03.11.2011, 10:27 4
Но мне нужно переделать её так, чтобы она работала на int64
Ну если ты понимаешь как работает ЭТА функция,
то это как бы очевидно как переделать

Разбивать число на 2
части не очень хотелось бы, чтобы не испортить быстродействие.
Ну как бы очевидно что на 64 разряда будет медленнее
0
4201 / 1793 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
03.11.2011, 10:31 5
Цитата Сообщение от nsuperman Посмотреть сообщение
У меня есть функция, которая считает количество бит в 32-х разрядном
А зачем их считать? Их всегда 32, это известно априорно.
0
Эксперт С++
7175 / 3234 / 80
Регистрация: 17.06.2009
Сообщений: 14,164
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;
0
4201 / 1793 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
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;
}
0
33 / 33 / 18
Регистрация: 15.05.2013
Сообщений: 236
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;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
24.05.2014, 14:46
Помогаю со студенческими работами здесь

Подсчет количества слов
Есть два файла, 1.txt и 2.txt Задание: 1) Скопировать в файл 2.txt только те строки из...

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

Подсчет количества слов
Допустим, дана строка: "129 s23 ertr 234 0 e" Как подсчитать количество слов, состоящих только...

Подсчёт количества символов
Здравствуйте, возник вопрос: Почему в функцию не передаётся вся строка, например я пишу "qwerty...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru