C как посчитать количество единичных битов

Сыну задали задачу — на чистом С получить для русского алфавита в ANSI и UNICODE кодировке таблицу: символ — битовое представление — количестов единиц в битовом представлении. Взялся ему помочь, но что-то не получилось.
char *p, bukv[1];
p = malloc(nbukv);
for(i=0;i bukv[0] = ‘\0’;
strncat(bukv, p, 1);
>> вот здесь хотелось бы обрабатывать bukv
p++;
>
Подскажите, пожалуйста, как решить эту задачу.

Сообщение отредактировано: tumanovalex — 21.09.08, 17:31
Сообщ. #2 , 21.09.08, 18:13

Senior Member
Рейтинг (т): 63
Для начала неплохо самому представить, что надо сделать. Код только какойто странный.
char *p, bukv[1];//Здесь точно ничего не напутали?
p = malloc(nbukv);//Не мало ли?
for(i=0; iНасчет русского алфавита — хм, в какой кодировке? Чтото сказали про UNICODE на чистом C(Имхо, юникодом и на «чистых» плюсах не пахнет)?

Сообщ. #3 , 21.09.08, 18:23
Рейтинг (т): нет
сдвига я не знаю
но можно сделать так
int a=100 ; //к примеру это входное число (код буквы)
int b=(a%2)+(a%4)+(a%8)+(a%16)+(a%32)+(a%64)+(a%128)+(a%256) // а это количество единиц

напоминаю операция % вычисление остатка от деления .Мож кто забыл

Добавлено 21.09.08, 18:25
сори там надо более хитроумное придумать с этим

Добавлено 21.09.08, 18:31
в цикле и с условием.

Сообщ. #4 , 21.09.08, 18:49
Рейтинг (т): 2

Пока хотелось бы решить задачу хотя бы для ANSI. Строка считывается из файла (для возможности ввода любого текста) в массив p, nbukv — количество символов в строке. p++ для того, чтобы передвигаться в строке, а bukv[1] для выделенного из строки символа. Может быть можно что-нибудь придумать получше и красивее, но так точно работает. Без bukv[0] = ‘\0’; получается ерунда. Чистый С подразумевает все остальное, кроме специфичных для Unicode функций (без С++). Может быть лучше мне было задать этот вопрос в Win32?

Сообщ. #5 , 21.09.08, 18:53
Рейтинг (т): 134
ИМХО лучшим вариантом подсчета единичных бит является алгоритм «разделяй и властвуй»
// для 16-х битных слов
int NumOfBits(unsigned int x) < x = x - ((x >> 1) & 0x5555);
x = (x + (x >> 4)) & 0x0f0f;

Не проверял, но по идее должно работать А уж преобразовать число в строку его бинарного представления думаю сам справишься.

две очепятки нашел. исправил

Сообщение отредактировано: AndNot — 21.09.08, 19:27
Сообщ. #6 , 22.09.08, 12:11
Рейтинг (т): 61

В принципе, все легко делается для обоих случаев.
Идешь по символам(просто индексируешь строку, в этом случае не нужно самому заботится о количесве байтов в ANSI и Unicode), каждый символ разбиваешь на байты(в случае ANSI у тебя будет один байт) или заводишь указатель на байт(char) и сравниваешь его значение с адресом следующего элемента строки, выполняешь подсчет единиц для каждого байта, складываешь — получаешь число единиц в конкретном символе.
Это общее решения для двух таблиц. Если бы ты на С++ писал, можно было бы и зашаблонить. А так можно или дефайн или копипаст.

Сообщ. #7 , 22.09.08, 12:40

Рейтинг (т): 231
можно табличкой))
unsigned bits [] = <0,1,1,2,1,2,2,3,1, 2,2,3,2,3,3,4,1,2,2,3,2,3,3,4, 2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3, 3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5, 4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4,3,4, 4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4, 4,5,4,5,5,6,4,5,5,6,5,6,6,7,1,2,2,3, 2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4, 4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5, 5,6,5,6,6,7,2,3,3,4,3,4,4,5,3,4,4,5, 4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6, 6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,>;
unsigned char c = ‘Б’;
std::cout << bits[c] << " " << unsigned (c);

Добавлено 22.09.08, 12:42
для юникода
bits[unsigned char ( c )] + bits[unsigned char (c >> 8)];

Сообщение отредактировано: LuckLess — 22.09.08, 13:04
Сообщ. #8 , 22.09.08, 12:50

Рейтинг (т): 150
int b=(a%2)+(a%4)+(a%8)+(a%16)+(a%32)+(a%64)+(a%128)+(a%256) // а это количество единиц

Скорре уж так
int b=(a&1)+(a&2)+(a&4)+(a&8)+(a&16)+(a&32)+(a&64)+(a&128)+(a&256) // а это количество единиц
Сообщение отредактировано: Hsilgos — 22.09.08, 13:19
Сообщ. #9 , 22.09.08, 12:55

Рейтинг (т): 506
Цитата Hsilgos @ 22.09.08, 12:50
Скорре уж так

Боюсь, что ни так, ни так не получится.
Сообщ. #10 , 22.09.08, 12:59
Рейтинг (т): 74
c 256 эндить не стоит
Сообщ. #11 , 22.09.08, 13:04

Рейтинг (т): 150
Боюсь, что ни так, ни так не получится.
Сообщ. #12 , 22.09.08, 13:05

Рейтинг (т): 231
Цитата Hsilgos @ 22.09.08, 12:50

Что ж ты так юникод не лубиш?

Добавлено 22.09.08, 13:05
да. с 256 перебрали малость

Сообщ. #13 , 22.09.08, 13:08
Рейтинг (т): 2

В конце концов я остановился на таком варианте (пока ANSI, дальше буду думать по поводу общей программы для ANSI и UNICODE):

while(!feof(pfile)) < c = fgetc(pfile); //CharToOem(c, c); printf("%c\t%i\t%-s\t\t%i\n", c, __toascii(c), _itoa(__toascii(c),s,2), get_bit_8(c)); short get_bit_8(char Data) < // авторство этой функции не помню, нашел в каком-то форуме unsigned short Mask = 0x80, Res=0, i; for (i = 0; i < 8; i++) < return Res;

Хотелось бы получить ответы на следующие вопросы:
1.Как перевести символ из CharToOem, чтобы на экране в консольном приложении видеть нормальные буквы (в документированной строке ошибка, как правильно сделать, я не знаю)?
2. Можно ли вместо __toascii© использовать какую-нибудь другую функцию, более современную (когда я делал без нее,_itoa давала ерунду)?
3. Как сделать так, чтобы в результате действия _itoa на экран выводились бы все входящие в двоичное представление нули? Сейчас для пробела (код 32) выводится 100000, выравнивание по левому краю (теряются нули слева и справа и для других символов);
4. При считывании из файла считывается, видимо, и символ конца файла (11111111). Можно ли так модифицировать кусок кода, чтобы он на печать не выводился?

Битовые операции III: подсчёт бит

Рассмотрим 8-битное число, составленное из бит с b₀ по b₇. Число установленных бит можно получить, сложив все разряды числа: b₀ + b₁ + … + b₇. Чётность равна остатку от деления этой суммы на 2. Иными словами, вместо сложения отдельных бит можно использовать операцию исключающее или, выполняющую сложение по модулю 2.

Благодаря ассоциативности и коммутативности сложения можно складывать биты в произвольном порядке, например, так: ((b₇ + b₆) + (b₅ + b₄)) + ((b₃ + b₂) + (b₁ + b₀)), то есть сложить пары соседних бит, потом соседние пары бит результата (из которых важен только младший бит), потом соседние четверки бит и т.д. Данный метод применим к произвольному числу бит и позволяет ускорить вычисление с помощью применения поразрядных операций, одновременно задействующих группы бит, уложенные в одном машинном слове.

Вариант для 32-битного числа (с каждым удвоением разрядности достаточно добавлять лишь одну строчку-комбинацию ^= и >> , их относительный порядок не играет роли):

inline unsigned parity(uint32_t bits) < bits ^= bits >> 1; // соседние биты bits ^= bits >> 2; // соседние пары бит bits ^= bits >> 4; // соседние четверки бит bits ^= bits >> 8; // соседние байты bits ^= bits >> 16; // соседние пары байт return bits & 1; // чётность в младшем бите >

Получить сумму младших бит во всех четвёрках бит числа можно одной операцией умножения на число, составленное из четвёрок бит 0001₂, длиной в машинное слово, при этом результат будет находиться в четырёх старших битах. Таким образом, вышеприведённый код можно заменить на следующий код. Этот код эффективнее, если целевой процессор умеет быстро умножать (что, в частности, справедливо для современных процессоров семейства x86).

inline unsigned parity(uint32_t bits) < bits ^= bits >> 1; // соседние биты bits ^= bits >> 2; // соседние пары бит bits = (bits & 0x1111'1111) * 0x1111'1111; return (bits >> 28) & 1; >

Другой способ оптимизации первого варианта parity не использует умножение и заключается в использовании 32-битного числа как таблицы бит чётности. (Данный способ позаимствован отсюда.)

inline unsigned parity(uint32_t bits) < bits ^= bits >> 16; bits ^= bits >> 8; bits ^= bits >> 4; return (0x6996u >> (bits & 0xF)) & 1; >

Наконец, если доступна быстрая функция определения числа установленных бит (например, реализованная через команду процессора), обозначенная здесь как bit_count , то достаточно взять младший бит её результата.

inline unsigned parity(uint32_t bits)

Определить число установленных бит

Относительно медленный, но элегантный и не зависящий от количества разрядов способ (предложен Б.Керниганом), снимающий в цикле по одному установленному биту (справа налево):

unsigned bit_count(unsigned bits)

Ещё один широко известный и популярный (например, встречается в реализациях стандартного класса bitset) метод заключается в использовании таблицы количеств бит для всех возможных значений одной тетрады и суммирования по тетрадам (опять же в цикле). Данный метод также не зависит от разрядности числа.

unsigned bit_count(unsigned bits) < static const unsigned nibble_count[] = < 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 >; unsigned counter = 0; while (bits != 0) < // взять младшую тетраду counter += nibble_count[bits & 0xF]; bits >>= 4; // отбросить младшую тетраду > return counter; >

«Параллельный» вариант, манипулирующий парами, четвёрками и т.д. бит (сразу немного оптимизированный):

inline unsigned bit_count(uint32_t bits) < unsigned counter = 0; counter = bits - ((bits >> 1) & 0x5555'5555); counter = ((counter >> 2) & 0x3333'3333) + (counter & 0x3333'3333); counter = ((counter >> 4) + counter) & 0x0F0F'0F0F; counter = ((counter >> 8) + counter) & 0x00FF'00FF; counter = ((counter >> 16) + counter) & 0x0000'FFFF; return counter; >

Его можно ещё слегка оптимизировать, если заметить, что по крайней мере одно наложение маски избыточно, так как переносы не пересекают последовательности нулевых бит:

inline unsigned bit_count(uint32_t bits) < unsigned counter = 0; counter = bits - ((bits >> 1) & 0x5555'5555); counter = ((counter >> 2) & 0x3333'3333) + (counter & 0x3333'3333); counter = ((counter >> 4) + counter) & 0x0F0F'0F0F; counter += counter >> 8; return (counter + (counter >> 16)) & 0x3F; >

Наконец, для процессоров, способных быстро умножать, может использоваться следующая версия:

inline unsigned bit_count(uint32_t bits) < bits = bits - ((bits >> 1) & 0x5555'5555); bits = (bits & 0x3333'3333) + ((bits >> 2) & 0x3333'3333); return ((bits + (bits >> 4) & 0x0F0F'0F0F) * 0x0101'0101) >> 24; >

Два последних варианта позаимствованы отсюда.

Ассемблерные аналоги x86: POPCNT.

Расстояние по Хэммингу

Вес строки бит по Хэммингу (норма) — количество единичных бит (см. предыдущий пример).

Расстояние между строками бит по Хэммингу (метрика) — количество различающихся бит в одинаковых позициях.

При наличии функции bit_count реализовать функцию, вычисляющую расстояние по Хэммингу между бит-строками, не представляет труда.

inline unsigned hamming_distance(uint32_t a, uint32_t b)

Определить номер самого правого установленного бита

Будем считать, что эта задача эквивалентна задаче вычисления количества идущих подряд младших нулевых бит (trailing zeroes), т.е. для нулевого аргумента ответ равен числу разрядов.

Простой и достаточно эффективный (из реализуемых стандартными операциями) способ на основе двоичного поиска, применённый к 32-битным числам.

inline unsigned trailing_zero_bits(uint32_t word) < if (word & 0x1) // половина чисел -- нечётные return 0; const auto old_word = word; unsigned bits = 1; if ((word & 0xFFFF) == 0) < word >>= 16; bits += 16; > if ((word & 0xFF) == 0) < word >>= 8; bits += 8; > if ((word & 0xF) == 0) < word >>= 4; bits += 4; > if ((word & 0x3) == 0) < word >>= 2; bits += 2; > return old_word? bits - (word & 0x1) : 32; >

Если же доступна эффективная реализация (командой процессора) операции вычисления числа установленных бит bit_count или операции leading_zero_bits , описанной в следующем разделе, то можно воспользоваться ими. Заметим, что изолировать младший ненулевой бит в числе x можно, вычислив (0 — x) & x . Если вычесть из этого числа единицу, то количество установленных бит будет равно искомому значению. Впрочем, то же самое можно получить более простым выражением (x — 1) & ~x .

inline unsigned trailing_zero_bits(unsigned word)

Вариант на основе leading_zero_bits потенциально менее эффективен, поскольку надо особым образом обрабатывать значение 0.

inline unsigned trailing_zero_bits(unsigned word)

Ассемблерные аналоги x86: BSF, TZCNT.

Определить номер самого левого установленного бита

Данная задача по сути эквивалентна задаче вычисления округлённого вниз двоичного логарифма числа и родственна задаче подсчёта количества идущих подряд нулевых старших бит (leading zeroes). Обе эти задачи могут решаться с помощью команд процессора (см. например: Википедия).

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

inline unsigned leading_zero_bits(uint32_t word) < const auto old_word = word; unsigned bits = 0; if ((word & 0xFFFF'0000) == 0) < word if ((word & 0xFF00'0000) == 0) < word if ((word & 0xF000'0000) == 0) < word if ((word & 0xC000'0000) == 0) < word const auto non_zero_bits = bits + ((word >> 31) == 0); return old_word? non_zero_bits: 32; >

Тот же метод для получения номера самого старшего установленного бита (ненулевой аргумент).

inline unsigned find_first_set(uint32_t word) < assert(word != 0); unsigned bit = 31; if ((word & 0xFFFF'0000) == 0) < word if ((word & 0xFF00'0000) == 0) < word if ((word & 0xF000'0000) == 0) < word if ((word & 0xC000'0000) == 0) < word return bit - (~word >> 31); >

При наличии эффективной реализации функции leading_zero_bits реализация find_first_set тривиальна.

inline unsigned find_first_set(uint32_t word)

Наконец, при наличии эффективной реализации функции bit_count , можно реализовать leading_zero_bits следующим образом (применив тот же приём, что и для вычисления ближайшей сверху степени двойки):

inline unsigned leading_zero_bits(uint32_t word) < word |= (word >> 1); word |= (word >> 2); word |= (word >> 4); word |= (word >> 8); word |= (word >> 16); return 32 - bit_count(word); >

Ассемблерные аналоги x86: BSR, LZCNT.

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

Нужно посчитать количество единичных бит, запрещается использовать любые арифметические операции (даже инкремент) и любые сторонние библиотеки (кроме iostream). Разрешается использование циклов и условных операторов. Входные данные: 7 Выходные данные: 3

#include using namespace std; int main()< int t,x = 0; cin >> x; while (x != 0) < t += 1; x &= x-1; >cout

Пытался делать, но получается только с инкрементом
Отслеживать
Ярик Иванов
задан 21 июн 2019 в 11:19
Ярик Иванов Ярик Иванов
51 4 4 бронзовых знака
Что именно не получается? Приведите пример кода, над которым работали.
21 июн 2019 в 11:24
Битовые операции разрешены?
21 июн 2019 в 11:31

Хм. полюбому в программе будет счётчик, и его придётся инкрементировать, а это арифметическая операция. Странная задача 🙂 Это вообще реально?

21 июн 2019 в 11:36
обожаю наше образование бессмысленное и беспощадное
21 июн 2019 в 12:05

Кусок кода — публиковать в вопрос. Будет тема для обсуждения. Два несвязаных куска кода которые в коментариях — ниочём не говорят.

Обстоятельно о подсчёте единичных битов

Я хотел бы подарить сообществу Хабра статью, в которой стараюсь дать достаточно полное описание подходов к алгоритмам подсчёта единичных битов в переменных размером от 8 до 64 битов. Эти алгоритмы относятся к разделу так называемой «битовой магии» или «битовой алхимии», которая завораживает своей красотой и неочевидностью многих программистов. Я хочу показать, что в основах этой алхимии нет ничего сложного, и вы даже сможете разработать собственные методы подсчёта единичных битов, познакомившись с фундаментальными приёмами, составляющими подобные алгоритмы.

Прежде чем мы начнём, я сразу хочу предупредить, что это статья не для новичков в программировании. Мне необходимо, чтобы читатель в общих чертах представлял себе простейшие битовые операции (побитовое «и», «или», сдвиг), хорошо владел шестнадцатеричной системой счисления и достаточно уверенно пользовался воображением, представляя в нём не всегда короткие битовые последовательности. По возможности, всё будет сопровождаться картинками, но сами понимаете, они лишь упрощают, но не заменяют полное представление.

Все описанные приёмы были реализованы на языке Си и протестированы в двух режимах: 32 и 64 бита. Таким образом, для более полного понимания статьи будет лучше, чтобы вы хотя бы приблизительно понимали язык Си. Тестирование проходило на процессоре Core 2 Duo E8400 @3GHz на 64-х битовой Windows 7. Измерение чистого времени работы программ проводилось с помощью утилиты runexe. Все исходные коды описываемых алгоритмов доступны в архиве на Яндекс диске, их компиляция проверена для компиляторов Visual C++, Intel C++, GCC и CLang, так что в принципе, проблем у вас быть не должно, если кто-то захочет перепроверить результаты у себя. Пользователи Linux, думаю, лучше меня знают, как им тестировать время работы программы у себя в системе, поэтому им советов не даю.

Среди читателей, возможно, будут такие, кому проще посмотреть всё то же самое на видео. Я записал такое видео (58 минут), в котором в формате презентации изложено в точности всё то же самое, что будет ниже по тексту, но может немного в другом стиле, более сухо и строго, тогда как текст я попытался немного оживить. Поэтому изучайте материал так, как кому удобнее.

Смотреть видео

Сейчас будут последовательно описаны алгоритмы, порождаемые тем или иным набором алхимических приёмов, в каждом разделе будет таблица сравнения времени работы для переменных разного размера, а в конце будет сводная таблица по всем алгоритмам. Во всех алгоритмах используются псевдонимы для чисел без знака от 8 до 64 бит.

typedef unsigned char u8; typedef unsigned short int u16; typedef unsigned int u32; typedef unsigned long long u64;

Наивный подход

Очевидно, что битовая алхимия применяется вовсе не для того, чтобы блистать на собеседовании, а с целью существенного ускорения программ. Ускорения по отношению к чему? По отношению к тривиальным приёмам, которые могут прийти в голову, когда нет времени более детально вникнуть в задачу. Таковым приёмом и является наивный подход к подсчёту битов: мы просто «откусываем» от числа один бит за другим и суммируем их, повторяя процедуру до тех пор, пока число не станет равным нулю.

u8 CountOnes0 (u8 n) < u8 res = 0; while (n) < res += n&1; n >>= 1; > return res; >

Я не вижу смысла что-либо комментировать в этом тривиальном цикле. Невооружённым взглядом ясно, что если старший бит числа n равен 1, то цикл вынужден будет пройтись по всем битам числа, прежде чем доберётся до старшего.

Меняя тип входного параметра u8 на u16, u32 и u64 мы получим 4 различные функции. Давайте протестируем каждую из них на потоке из 2 32 чисел, подаваемых в хаотичном порядке. Понятно, что для u8 у нас 256 различных входных данных, но для единообразия мы всё равно прогоняем 2 32 случайных чисел для всех этих и всех последующих функций, причём всегда в одном и том же порядке (за подробностями можно обратиться к коду учебной программы из архива).

Время в таблице ниже указано в секундах. Для тестирования программа запускалась трижды и выбиралось среднее время. Погрешность едва ли превышает 0,1 секунды. Первый столбец отражает режим компилятора (32-х битовый исходный код или 64-х битовый), далее 4 столбца отвечают за 4 варианта входных данных.

Режим	u8	u16	u32	u64
x86	38,18	72,00	130,49	384,76
x64	37,72	71,51	131,47	227,46

Как мы видим, скорость работы вполне закономерно возрастает с ростом размера входного параметра. Немного выбивается из общей закономерности вариант, когда числа имеют размер 64 бита, а подсчёт идёт режиме x86. Ясное дело, что процессор вынужден делать четырёхкратную работу при удвоении входного параметра и даже хорошо, что он справляется всего лишь втрое медленнее.

Первая польза этого подхода в том, что при его реализации трудно ошибиться, поэтому написанная таким образом программа может стать эталонной для проверки более сложных алгоритмов (именно так и было сделано в моём случае). Вторая польза в универсальности и относительно простой переносимости на числа любого размера.

Трюк с «откусыванием» младших единичных битов

Этот алхимический приём основан на идее обнуления младшего единичного бита. Имея число n, мы можем произнести заклинание n=n&(n-1), забирая у числа n его младшую единичку. Картинка ниже для n=232 прояснит ситуацию для людей, впервые узнавших об этом трюке.

Код программы не сильно изменился.

u8 CountOnes1 (u8 n) < u8 res = 0; while (n) < res ++; n &= n-1; // Забираем младшую единичку. >return res; >

Теперь цикл выполнится ровно столько раз, сколько единиц в числе n. Это не избавляет от худшего случая, когда все биты в числе единичные, но значительно сокращает среднее число итераций. Сильно ли данный подход облегчит страдания процессора? На самом деле не очень, а для 8 бит будет даже хуже. Напомню, что сводная таблица результатов будет в конце, а здесь в каждом разделе будет своя таблица.

Режим	u8	u16	u32	u64
x86	44,73	55,88	72,02	300,78
x64	40,96	69,16	79,13	126,72

Предподсчёт

Не будем торопиться переходить к «жёстким» заклинаниям, рассмотрим последний простой приём, который может спасти даже самого неопытного мага. Данный вариант решения задачи не относится напрямую к битовой алхимии, однако для полноты картины должен быть рассмотрен в обязательном порядке. Заведём две таблицы на 256 и 65536 значений, в которых заранее посчитаны ответы для всех возможных 1-байтовых и 2-байтовых величин соответственно.

 u8 BitsSetTableFF[256]; // Здесь все ответы для одного байта u8 BitsSetTableFFFF[65536]; // Здесь все ответы для двух байт

Теперь программа для 1 байта будет выглядеть так

 u8 CountOnes2_FF (u8 n)

Чтобы рассчитать число бит в более крупных по размеру числах, их нужно разбить на байты. Например, для u32 может быть вот такой код:

 u8 CountOnes2_FF (u32 n)

Или такой, если мы применяем таблицу предподсчёта для 2-х байт:

 u8 CountOnes2_FFFF (u32 n)

Ну а дальше вы догадались, для каждого варианта размера входного параметра n (кроме 8 бит) может существовать два варианта предподсчёта, в зависимости от того, которую из двух таблиц мы применяем. Думаю, читателю понятно, почему мы не можем просто так взять и завести таблицу BitsSetTableFFFFFFFF, однако вполне могут существовать задачи, где и это будет оправданным.

Быстро ли работает предподсчёт? Всё сильно зависит от размера, смотрите таблицы ниже. Первая для однобайтового предподсчёта, а вторая для двухбайтового.

Режим	u8	u16	u32	u64
x86	0,01	1,83	21,07	36,25
x64	0,01	1,44	24,79	26,84

Интересный момент: для режима x64 предподсчёт для u64 работает заметно быстрее, возможно, это особенности оптимизации, хотя подобное не проявляется во втором случае.

Режим	u8	u16	u32	u64
x86	—	0,05	7,95	13,01
x64	—	0,07	8,49	13,01

Важное замечание: данный алгоритм с использованием предподсчёта оказывается выгодным только лишь при соблюдении следующих двух условий: (1) у вас есть лишняя память, (2) вам требуется выполнять расчёт числа единичных битов намного больше раз, чем размер самой таблицы, то есть имеется возможность «отыграть» время, потраченное на предварительное заполнение таблицы каким-то из нехитрых алгоритмов. Пожалуй, можно также иметь в виду экзотическое условие, которое на практике всегда выполнено. Вы должны гарантировать, что обращение к памяти само по себе быстрое и не замедляет работу других функций системы. Дело в том, что обращение к таблице может выбросить из кэша то, что там было изначально и замедлить таким образом какой-то другой участок кода. Косяк это вы вряд ли найдёте быстро, однако подобные чудовищные оптимизации едва ли кому-то понадобятся на практике при реализации обычных программ.

Умножение и остаток от деления

Возьмем же наконец более сильные зелья с нашей алхимической полки. С помощью умножения и остатка от деления на степень двойки без единицы можно делать довольно интересные вещи. Начнём творить заклинание с одного байта. Для удобства обозначим все биты одного байта латинскими буквами от «a» до «h». Наше число n примет вид:

Умножение n’ = n⋅0x010101 (так, через префикс «0x», я обозначаю шестнадцатеричные числа) делает ни что иное как «тиражирование» одного байта в трёх экземплярах:

Теперь разобьём мысленно наши 24 бита на 8 блоков по 3 бита в каждом (см. нижеследующую картинку, первую строку таблички). Затем с помощью побитового «и» с маской 0x249249 (вторая строка таблички) обнулим в каждом блоке два старших бита.

Третья строка таблицы поясняет шестнадцатеричную запись маски. В последней строке показан результат, которого мы добивались: все биты исходного байта содержаться каждый в своём трёхбитовом блоке, но в ином порядке (порядок нам и не важен).

Теперь внимание: мы должны сложить эти 8 блоков – и получим сумму наших бит!

Оказывается, что остаток от деления некоторого числа A на 2 k -1 как раз даёт сумму k-битовых блоков числа A, тоже взятую по модулю 2 k -1.

Разобьём число A (в двоичной записи) на блоки по k бит в каждом (при необходимости можно дополнить самый последний, старший, блок нулями). Обозначим через A_i i-й блок. Теперь запишем значение числа A через сумму этих блоков, помноженных на соответствующую степень двойки:
A= A₀⋅2 0⋅k + A₁⋅2 1⋅k +…+ A_N-1⋅2 (N-1)⋅k ,
где N – число блоков.
Теперь рассчитаем A mod (2 k -1).
A mod (2 k -1)= (A₀⋅2 0⋅k + A₁⋅2 1⋅k +…+ A_N-1⋅2 (N-1)⋅k ) mod (2 k -1) = (A₀+ A₁+…+ A_N-1) mod (2 k -1).
Всё благодаря тому, что 2 i⋅k = 1 (mod (2 k -1)) для любого целого неотрицательного i. (Здесь, правда, важно, что трюк имеет смысл, когда k>1, иначе не совсем понятно как нам интерпретировать модуль 1). Вот мы и получили сумму блоков по модулю 2 k -1.

То есть от полученного нами числа нужно взять остаток от деления на 2 3 -1 (семь) — и мы получаем сумму наших 8-и блоков по модулю 7. Беда в том, что сумма бит может быть равна 7 или 8, в таком случае алгоритм выдаст 0 и 1 соответственно. Но давайте посмотрим: в каком случае мы можем получить ответ 8? Только когда n=255. А в каком случае можем получить 0? Только когда n=0. Поэтому если алгоритм после взятия остатка на 7 даст 0, то либо мы на входе получили n=0, либо в числе ровно 7 единичных бит. Суммируя эту рассуждение, получаем следующий код:

u8 CountOnes3 (u8 n) < if (n == 0) return 0; // Единственный случай, когда ответ 0. if (n == 0xFF) return 8; // Единственный случай, когда ответ 8. n = (0x010101*n & 0x249249) % 7; // Считаем число бит по модулю 7. if (n == 0) return 7; // Гарантированно имеем 7 единичных битов. return n; // Случай, когда в числе от 1 до 6 единичных битов. >

В случае когда n имеет размер 16 бит можно разбить его на две части по 8 бит. Например, так:

u8 CountOnes3 (u16 n) < return CountOnes3 (u8(n&0xFF)) + CountOnes3 (u8(n>>8));

Для случая 32-х и 64-х бит подобное разбиение не имеет смысла уже даже в теории, умножение и остаток от деления с тремя ветвлениями будут слишком дорого стоить, если выполнять их 4 или 8 раз подряд. Но я оставил для вас пустые места в нижеследующей таблице, поэтому если вы мне не верите – заполните их, пожалуйста, сами. Там скорее всего будут результаты, сравнимые с процедурой CountBits1, если у вас похожий процессор (я не говорю о том, что здесь возможны оптимизации с помощью SSE, это уже будет другой разговор).

Режим	u8	u16	u32	u64
x86	12,42	30,57	—	—
x64	13,88	33,88	—	—

Данный трюк, конечно, можно сделать и без ветвлений, но тогда нам нужно, чтобы при разбиении числа на блоки в блок вместились все числа от 0 до 8, а этого можно добиться лишь в случае 4-битовых блоков (и больше). Чтобы выполнить суммирование 4-битовых блоков, нужно подобрать множитель, который позволит правильно «растиражировать» число и взять остаток от деления на 2 4 -1=15, чтобы сложить получившиеся блоки. Опытный алхимик (который знает математику) легко подберёт такой множитель: 0x08040201. Почему он выбран таким?

Дело в том, что нам необходимо, чтобы все биты исходного числа заняли правильные позиции в своих 4-битовых блоках (картинка выше), а коль скоро 8 и 4 не являются взаимно простыми числами, обычное копирование 8 битов 4 раза не даст правильного расположения нужных битов. Нам придётся добавить к нашему байту один нолик, то есть тиражировать 9 битов, так как 9 взаимно просто с 4. Так мы получим число, имеющее размер 36 бит, но в котором все биты исходного байта стоят на младших позициях 4-битовых блоков. Осталось только взять побитовое «и» с числом 0x111111111 (вторая строка на картинке выше), чтобы обнулить по три старших бита в каждом блоке. Затем блоки нужно сложить.

При таком подходе программа подсчёта единичных битов в байте будет предельно простой:

u8 CountOnes3_x64 (u8 n)

Недостаток программы очевиден: требуется выход в 64-битовую арифметику со всеми вытекающими отсюда последствиями. Можно заметить, что в действительности данная программа задействует только 33 бита из 64-х (старшие 3 бита обнуляются), и в принципе можно сообразить, как перенести данные вычисления в 32-х битовую арифметику, но рассказы о подобных оптимизациях не входят в тему этого руководства. Давайте пока просто изучать приёмы, а оптимизировать их вам придётся самим уже под конкретную задачу.

Ответим на вопрос о том, какого размера может быть переменная n, чтобы данный трюк правильно работал для неё. Коль скоро мы берём остаток от деления на 15, такая переменная не может иметь размер больше 14 бит, в противном случае придётся применить ветвление, как мы делали это раньше. Но для 14 бит приём работает, если добавить к 14-ти битам один нолик, чтобы все биты встали на свои позиции. Теперь я буду считать, что вы в целом усвоили суть приёма и сможете сами без труда подобрать множитель для тиражирования и маску для обнуления ненужных битов. Покажу сразу готовый результат.

u8 CountOnes3_x64 (u14 n) < // Это не опечатка (и не должно работать)! return (n*0x200040008001llu & 0x111111111111111llu) % 15; >

Эта программа выше показывает, как мог бы выглядеть код, будь у вас переменная размером 14 бит без знака. Этот же код будет работать с переменной в 15 бит, но при условии, что максимум лишь 14 из них равные единице, либо если случай, когда n=0x7FFF мы разберём отдельно. Это всё нужно понимать для того, чтобы написать правильный код для переменной типа u16. Идея в том, чтобы сначала «откусить» младший бит, посчитать биты в оставшемся 15-ти битовом числе, а затем обратно прибавить «откушенный» бит.

u8 CountOnes3_x64 (u16 n) < u8 leastBit = n&1; // Берём младший бит. n >>= 1; // Оставляем только 15 бит исходного числа. if (n == 0) return leastBit; // Если получился 0, значит ответом будет младший бит. if (n == 0x7FFF) return leastBit + 15; // Единственный случай, когда ответ 15+младший бит. return leastBit + (n*0x200040008001llu & 0x111111111111111llu) % 15; // Ответ (максимум 14+младший бит). >

Для n размером 32 бита приходится колдовать уже с более серьёзным лицом… Во-первых, ответ влезает только в 6 бит, но можно рассмотреть отдельный случай, когда n=2 32 -1 и спокойно делать расчёты в полях размером 5 бит. Это экономит место и разрешает нам разбить 32-битовое поле числа n на 3 части по 12 бит в каждой (да, последнее поле будет не полным). Поскольку 12⋅5=60, мы можем тиражировать одно 12-битовое поле 5 раз, подобрав множитель, а затем сложить 5-битовые блоки, взяв остаток от деления на 31. Сделать это нужно 3 раза для каждого поля. Суммируя итог, получаем такой код:

u8 CountOnes3_x64 ( u32 n ) < if (n == 0) return 0; if (n + 1 == 0) return 32; u64 res = (n&0xFFF)*0x1001001001001llu & 0x84210842108421llu; res += ((n&0xFFF000)>>12)*0x1001001001001llu & 0x84210842108421llu; res += (n>>24)*0x1001001001001llu & 0x84210842108421llu; res %= 0x1F; if (res == 0) return 31; return res; >

Здесь точно также можно было вместо трех ветвлений взять 3 остатка от деления, но я выбрал ветвистый вариант, на моём процессоре он будет работать лучше.

Для n размером 64 бита мне не удалось придумать подходящего заклинания, в котором было бы не так много умножений и сложений. Получалось либо 6, либо 7, а это слишком много для такой задачи. Другой вариант — выход в 128-битовую арифметику, а это уже не пойми каким «откатом» для нас обернётся, неподготовленного мага может и к стенке отшвырнуть 🙂

Давайте лучше посмотрим на время работы.

Режим	u8	u16	u32	u64
x86	39,78	60,48	146,78	—
x64	6,78	12,28	31,12	—

Очевидным выводом из этой таблицы будет то, что 64-х битовая арифметика плохо воспринимается в 32-х битовом режиме исполнения, хотя в целом-то алгоритм неплох. Если вспомнить скорость алгоритма предподсчёта в режиме x64 для однобайтовой таблицы для случая u32 (24,79 с), то получим, что данный алгоритм отстаёт всего лишь на 25%, а это повод к соревнованию, воплощённому в следующем разделе.

Замена взятия остатка на умножение и сдвиг

Недостаток операции взятия остатка всем очевиден. Это деление, а деление – это долго. Разумеется, современные компиляторы знают алхимию и умеют заменять деление на умножение со сдвигом, а чтобы получить остаток, нужно вычесть из делимого частное, умноженное на делитель. Тем не менее, это всё равно долго! Оказывается, что в древних свитках заклинателей кода сохранился один интересный способ оптимизации предыдущего алгоритма. Мы можем суммировать k-битовые блоки не взятием остатка от деления, а ещё одним умножением на маску, с помощью которой обнуляли лишние биты в блоках. Вот как это выглядит для n размером в 1 байт.

Для начала снова тиражируем байт трижды и удаляем по два старших бита у каждого 3-битового блока с помощью уже пройденной выше формулы 0x010101⋅n & 0x249249.

Каждый трёхбитовый блок я для удобства обозначил заглавной латинской буквой. Теперь умножаем полученный результат на ту же самую маску 0x249249. Маска содержит единичный бит в каждой 3-й позиции, поэтому такое умножение эквивалентно сложению числа самого с собой 8 раз, каждый раз со сдвигом на 3 бита:

Что мы видим? Биты с 21 по 23 и дают нам нужную сумму! При этом переполнения в каком-либо из блоков справа невозможно, так как там ни в одном блоке не будет числа, большего 7. Проблема лишь в том, что если наша сумма равна 8, мы получим 0, но это не страшно, ведь этот единственный случай можно рассмотреть отдельно.

u8 CountOnes3_x64_m (u8 n) < if (n == 0xFF) return 8; return ((u64(0x010101*n & 0x249249) * 0x249249) >> 21) & 0x7; >

По сути, мы взяли код из предыдущего раздела и заменили в нём взятие остатка от деления на 7 на умножение, сдвиг и побитовое «И» в конце. При этом вместо 3-х ветвлений осталось лишь одно.

Чтобы составить аналогичную программу для 16 бит, нам нужно взять код из предыдущего раздела, в котором показано как это делается с помощью взятия остатка от деления на 15 и заменить данную процедуру умножением. При этом нетрудно заметить то, какие условия можно убрать из кода.

u8 CountOnes3_x64_m (u16 n) < u8 leastBit = n&1; // Берём младший бит n >>= 1; // Оставляем только 15 бит. return leastBit + (( (n*0x200040008001llu & 0x111111111111111llu)*0x111111111111111llu >> 56) & 0xF); // Ответ (максимум 15 + младший бит). >

Для 32-х бит мы делаем то же самое: берём код из предыдущего раздела и, порисовав немного на бумаге, соображаем, каким будет сдвиг, если заменить остаток на умножение.

u8 CountOnes3_x64_m ( u32 n ) < if (n+1 == 0) return 32; u64 res = (n&0xFFF)*0x1001001001001llu & 0x84210842108421llu; res += ((n&0xFFF000)>>12)*0x1001001001001llu & 0x84210842108421llu; res += (n>>24)*0x1001001001001llu & 0x84210842108421llu; return (res*0x84210842108421llu >> 55) & 0x1F; >

Для 64-х бит я тоже не смог придумать чего-то такого, чтобы не заставляло бы мой процессор выполнять роль печки.

Режим	u8	u16	u32	u64
x86	12,66	42,37	99,90	—
x64	3,54	4,51	18,35	—

Приятно удивили результаты для режима x64. Как и ожидалось, мы обогнали предподсчёт с однобайтовой таблицей для случая u32. Можно ли вообще обогнать предподсчёт? Хороший вопрос 🙂

Параллельное суммирование

Пожалуй, это самый распространённый трюк, который очень часто повторяют друг за другом не вполне опытные заклинатели, не понимая, как он точно работает.

Начнём с 1 байта. Байт состоит из 4-х полей по 2 бита, сначала просуммируем биты в этих полях, произнеся что-то вроде:

n = (n>>1)&0x55 + (n&0x55);

Вот пояснительная картинка к данной операции (по-прежнему, обозначаем биты одного байта первыми латинскими буквами):

Одно из побитовых «И» оставляет только младшие биты каждого двухбитового блока, второе оставляет старшие биты, но сдвигает их на позиции, соответствующие младшим битам. В результате суммирования получаем сумму смежных битов в каждом двухбитовом блоке (последняя строка на картинке выше).

Теперь сложим парами числа, находящиеся в двухбитовых полях, помещая результат в 2 четырёхбитовых поля:

n = (n>>2)&0x33 + (n&0x33);

Нижеследующая картинка поясняет результат. Привожу её теперь без лишних слов:

Наконец, сложим два числа в четырёхбитовых полях:

n = (n>>4)&0x0F + (n&0x0F);

Действуя по аналогии, можно распространить приём на любое число бит, равное степени двойки. Число строк заклинания равно двоичному логарифму от числа бит. Уловив идею, взгляните вскользь на 4 функции, записанных ниже, чтобы убедиться в правильности своего понимания.

u8 CountOnes4 (u8 n) < n = ((n>>1) & 0x55) + (n & 0x55); n = ((n>>2) & 0x33) + (n & 0x33); n = ((n>>4) & 0x0F) + (n & 0x0F); return n; >

u8 CountOnes4 (u16 n) < n = ((n>>1) & 0x5555) + (n & 0x5555); n = ((n>>2) & 0x3333) + (n & 0x3333); n = ((n>>4) & 0x0F0F) + (n & 0x0F0F); n = ((n>>8) & 0x00FF) + (n & 0x00FF); return n; >

u8 CountOnes4 (u32 n) < n = ((n>>1) & 0x55555555) + (n & 0x55555555); n = ((n>>2) & 0x33333333) + (n & 0x33333333); n = ((n>>4) & 0x0F0F0F0F) + (n & 0x0F0F0F0F); n = ((n>>8) & 0x00FF00FF) + (n & 0x00FF00FF); n = ((n>>16) & 0x0000FFFF) + (n & 0x0000FFFF); return n; >

u8 CountOnes4 (u64 n) < n = ((n>>1) & 0x5555555555555555llu) + (n & 0x5555555555555555llu); n = ((n>>2) & 0x3333333333333333llu) + (n & 0x3333333333333333llu); n = ((n>>4) & 0x0F0F0F0F0F0F0F0Fllu) + (n & 0x0F0F0F0F0F0F0F0Fllu); n = ((n>>8) & 0x00FF00FF00FF00FFllu) + (n & 0x00FF00FF00FF00FFllu); n = ((n>>16) & 0x0000FFFF0000FFFFllu) + (n & 0x0000FFFF0000FFFFllu); n = ((n>>32) & 0x00000000FFFFFFFFllu) + (n & 0x00000000FFFFFFFFllu); return n; >

На этом параллельное суммирование не заканчивается. Развить идею позволяет то наблюдение, что в каждой строчке дважды используется одна и та же битовая маска, что как будто наводит на мысль «а нельзя ли как-нибудь только один раз выполнить побитовое «И»?». Можно, но не сразу. Вот что можно сделать, если взять в качестве примера код для u32 (смотрите комментарии).

u8 CountOnes4 (u32 n) < n = ((n>>1) & 0x55555555) + (n & 0x55555555); // Можно заменить на разность n = ((n>>2) & 0x33333333) + (n & 0x33333333); // Нельзя исправить n = ((n>>4) & 0x0F0F0F0F) + (n & 0x0F0F0F0F); // Можно вынести & за скобку n = ((n>>8) & 0x00FF00FF) + (n & 0x00FF00FF); // Можно вынести & за скобку n = ((n>>16) & 0x0000FFFF) + (n & 0x0000FFFF); // Можно вообще убрать & return n; // Неявное обрезание по 8-и младшим битам. >

В качестве упражнения я бы хотел предложить доказать самостоятельно то, почему нижеследующий код будет точным отображением предыдущего. Для первой строки я даю подсказку, но не смотрите в неё сразу:

Подсказка
Двухбитовый блок ab имеет точное значение 2a+b, значит вычитание сделает его равным…?

u8 CountOnes4_opt (u32 n) < n -= (n>>1) & 0x55555555; n = ((n>>2) & 0x33333333 ) + (n & 0x33333333); n = ((n>>4) + n) & 0x0F0F0F0F; n = ((n>>8) + n) & 0x00FF00FF; n = ((n>>16) + n); return n; >

Аналогичные варианты оптимизации возможны и для остальных типов данных.

Ниже приводятся две таблицы: одна для обычного параллельного суммирования, а вторая для оптимизированного.

Режим	u8	u16	u32	u64
x86	7,52	14,10	21,12	62,70
x64	8,06	11,89	21,30	22,59

Режим	u8	u16	u32	u64
x86	7,18	11,89	18,86	65,00
x64	8,09	10,27	19,20	19,20

В целом мы видим, что оптимизированный алгоритм работает хорошо, но проигрывает обычному в режиме x86 для u64.

Комбинированный метод

Мы видим, что наилучшие варианты подсчёта единичных битов – это параллельный метод (с оптимизацией) и метод тиражирования с умножением для подсчёта суммы блоков. Мы можем объединить оба метода, получая комбинированный алгоритм.

Первое, что нужно сделать — выполнить первые три строки параллельного алгоритма. Это даст нам точную сумму битов в каждом байте числа. Например, для u32 выполним следующее:

 n -= (n>>1) & 0x55555555; n = ((n>>2) & 0x33333333) + (n & 0x33333333); n = (((n>>4) + n) & 0x0F0F0F0F );

Теперь наше число n состоит из 4 байт, которые следует рассматривать как 4 числа, сумму которых мы ищем:

Мы можем найти сумму этих 4-х байт, если умножим число n на 0x01010101. Вы теперь хорошо понимаете, что означает такое умножение, для удобства определения позиции, в которой будет находиться ответ, привожу картинку:

Ответ находится в 3-байте (если считать их от 0). Таким образом, комбинированный приём для u32 будет выглядеть так:

u8 CountOnes5 ( u32 n ) < n -= (n>>1) & 0x55555555; n = ((n>>2) & 0x33333333 ) + (n & 0x33333333); n = ((((n>>4) + n) & 0x0F0F0F0F) * 0x01010101) >> 24; return n; // Здесь происходит неявное обрезание по 8 младшим битам. >

Он же для u16:

u8 CountOnes5 (u16 n) < n -= (n>>1) & 0x5555; n = ((n>>2) & 0x3333) + (n & 0x3333); n = ((((n>>4) + n) & 0x0F0F) * 0x0101) >> 8; return n; // Здесь происходит неявное обрезание по 8 младшим битам. >

Он же для u64:

u8 CountOnes5 ( u64 n ) < n -= (n>>1) & 0x5555555555555555llu; n = ((n>>2) & 0x3333333333333333llu ) + (n & 0x3333333333333333llu); n = ((((n>>4) + n) & 0x0F0F0F0F0F0F0F0Fllu) * 0x0101010101010101) >> 56; return n; // Здесь происходит неявное обрезание по 8 младшим битам. >

Скорость работы этого метода вы можете посмотреть сразу в итоговой таблице.

Итоговое сравнение

Я предлагаю читателю самостоятельно сделать интересующие его выводы, изучив две нижеследующие таблицы. В них я обозначил название методов, программы к которым мы реализовали, а также пометил прямоугольной рамкой те подходы, которые я считаю наилучшими в каждом конкретном случае. Тех, кто думал, что предподсчёт всегда выигрывает, ожидает небольшой сюрприз для режима x64.

Итоговое сравнения для режима компиляции x86.

Итоговое сравнения для режима компиляции x64.

Замечание

Ни в коем случае не рассматривайте итоговую таблицу как доказательство в пользу того или иного подхода. Поверьте, что на вашем процессоре и с вашим компилятором некоторые числа в такой таблице будут совершенно иными. К сожалению, мы никогда не можем точно сказать, который из алгоритмов окажется лучше в том или ином случае. Под каждую задачу нужно затачивать конкретный метод, а универсального быстрого алгоритма, к сожалению, не существует.

Я изложил те идеи, о которых знаю сам, но это лишь идеи, конкретные реализации которых в разных комбинациях могут быть очень разными. Объединяя эти идеи разными способами, вы можете получать огромное количество разных алгоритмов подсчёта единичных битов, каждый из которых вполне может оказаться хорошим в каком-то своём случае.

Спасибо за внимание. До новых встреч!

UPD: Инструкция POPCNT из SSE4.2 не включена в список тестирования, потому что у меня нет процессора, который поддерживает SSE4.2.

битовые трюки
подсчёт битов
битовая магия
битовая алхимия

Спортивное программирование
Программирование
Алгоритмы

C как посчитать количество единичных битов