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

@nsuperman · Регистрация: 13.06.2011

Студворк — интернет-сервис помощи студентам

Здравствуйте!
У меня есть функция, которая считает количество бит в 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
части не очень хотелось бы, чтобы не испортить быстродействие.

Евгений М. · 02.11.2011, 04:29

Сообщение от nsuperman

У меня есть функция, которая считает количество бит в 32-х разрядном
числе типа uint

Количество бит в n-х разрядном числе разве не равен n?

@nsuperman · 02.11.2011, 20:36 **[ТС]**

Ой, я имею в виду, конечно, количества единиц, т.е. бит, равных единице.

@odip · 03.11.2011, 10:27

Но мне нужно переделать её так, чтобы она работала на int64

Ну если ты понимаешь как работает ЭТА функция,
то это как бы очевидно как переделать

Разбивать число на 2
части не очень хотелось бы, чтобы не испортить быстродействие.

Ну как бы очевидно что на 64 разряда будет медленнее

@taras atavin · 03.11.2011, 10:31

Сообщение от nsuperman

У меня есть функция, которая считает количество бит в 32-х разрядном

А зачем их считать? Их всегда 32, это известно априорно.

@odip · 03.11.2011, 10:32

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

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 · 03.11.2011, 10:40

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;
}

@Kant · 24.05.2014, 14:46

Не правильно.

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;
}

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

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

	Подсчет количества бит 02.11.2011, 01:47. Показов 4706. Ответов 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

@nsuperman 0 / 0 / 0 Регистрация: 13.06.2011 Сообщений: 4
	02.11.2011, 20:36 [ТС]
	Ой, я имею в виду, конечно, количества единиц, т.е. бит, равных единице. 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	03.11.2011, 10:32
	Не знаю будет быстрее или нет, можно попробовать такой способ 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