Статья @Zealint унесена мною с хабра Было бы жалко, если «моя прелесть» потеряется
​

Статья, в которой дано достаточно полное описание подходов к алгоритмам подсчета единичных битов в переменных размером от 8 до 64 битов. Алгоритмы относятся к так называемой «битовой магии» или «битовой алхимии», которая завораживает своей красотой и неочевидностью. В этой алхимии нет ничего сложного, и вы сможете разработать собственные методы подсчета единичных битов, познакомившись с фундаментальными приемами, составляющими подобные алгоритмы.
Это статья не для новичков в программировании. Необходимо, чтобы читатель в общих чертах представлял себе простейшие битовые операции («и», «или», сдвиг), владел шестнадцатеричной системой счисления и пользовался воображением, представляя не всегда короткие битовые последовательности. По возможности, всё будет сопровождаться таблицами, но они лишь упрощают, но не заменяют полное представление.
Описанные приемы были реализованы на языке Си и протестированы в режимах 32 и 64 бита. Для более полного понимания статьи необходимо, чтобы вы хотя бы приблизительно понимали язык Си. Тестирование проходило на процессоре Core 2 Duo E8400 @3GHz на 64-х битовой Windows 7. Измерение чистого времени работы программ проводилось с помощью утилиты runexe. Все исходные коды описываемых алгоритмов были доступны в архиве (https://yadi.sk/d/XiHe6MNtomAeh) на Яндекс диске, их компиляция проверена для компиляторов Visual C++, Intel C++, GCC и CLang (на данный момент архив не доступен).
Возможно, будут такие, кому проще посмотреть всё то же самое на видео. В 58 минутном видео изложено то же самое, но более сухо и строго.

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

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

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

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

Код (C):

1. u8 CountOnes0 (u8 n) {
2.   u8 res = 0;
3.   while (n) {
4.     res += n&1;
5.     n >>= 1;
6.   }
7.   return res;
8. }

Нет смысла что-либо комментировать в этом цикле. Если старший бит числа n равен 1, то цикл вынужден будет пройтись по всем битам числа, прежде чем доберется до старшего.
Меняя тип входного параметра u8 на u16, u32 и u64 получим 4 различные функции. Протестируем каждую из них на потоке из 2³² чисел, подаваемых в хаотичном порядке. Для u8 имеем 256 различных входных данных, но для единообразия прогоняем 2³² случайных чисел для этих и всех последующих функций, всегда в одном и том же порядке (за подробностями можно обратиться к коду учебной программы из архива).
Время в таблице указано в секундах. Для тестирования программа запускалась трижды и выбиралось среднее время. Погрешность не превышает 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, можем произвести [math]n=n\&(n-1)[/math], забирая у числа n его младшую единичку. Таблица ниже для [math]n[/math] = 0E8h = 11101000b прояснит ситуацию для людей, впервые узнавших об этом трюке.

	bin		hex
n	1110	1000	E8​
n-1	1110	0111	E7​
n&(n-1)	1110	0000	E0​

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

Код (C):

1. u8 CountOnes1 (u8 n) {
2.  u8 res = 0;
3.  while (n) {
4.  res ++;
5.  n &= n-1; // Забираем младшую единичку.
6.  }
7.  return res;
8. }

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

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

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

Код (C):

1. u8 CountOnes1 (u8 n) {
2.  u8 res = 0;
3.  while (n) {
4.  res ++;
5.  n &= n-1; // Забираем младшую единичку.
6.  }
7.  return res;
8. }

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

Предподсчет

Рассмотрим простой прием, который может спасти даже самого неопытного мага. Заведем две таблицы на 256 (=2⁸) и 65536 (=2¹⁶) значений, в которых заранее посчитаны ответы для всех возможных 1-байтовых и 2-байтовых величин соответственно.

Код (C):

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

Программа для 1 байта выглядит так

Код (C):

1. u8 CountOnes2_FF (u8 n) {
2.     return BitsSetTableFF[n];
3.   }

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

Код (C):

1. u8 CountOnes2_FF (u32 n) {
2.     u8 *p = (u8*)&n;
3.     n = BitsSetTableFF[p[0]]
4.       + BitsSetTableFF[p[1]]
5.       + BitsSetTableFF[p[2]]
6.       + BitsSetTableFF[p[3]];
7.     return n;
8.   }

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

Код (C):

1.   u8 CountOnes2_FFFF (u32 n) {
2.     u16 *p = (u16*)&n;
3.     n = BitsSetTableFFFF[p[0]]
4.       + BitsSetTableFFFF[p[1]];
5.     return n;
6.   }

Для каждого варианта размера входного параметра n (кроме 8 бит) может существовать два варианта предподсчета, в зависимости от того, которую из двух таблиц применяют. Понятно, почему не можем завести таблицу BitsSetTableFFFFFFFF, вполне могут существовать задачи, где это будет оправданным.
Быстро ли работает предподсчет? Это сильно зависит от размера числа. Первая таблица для 1 байтового предподсчета, вторая для 2-х байтового.

Режим	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. вам требуется выполнять расчет числа единичных битов намного больше раз, чем размер самой таблицы, то есть имеется возможность «отыграть» время, потраченное на предварительное заполнение таблицы каким-то из нехитрых алгоритмов.
3. экзотическое условие, которое на практике всегда выполнено. Вы должны гарантировать, что обращение к памяти само по себе быстрое и не замедляет работу других функций системы. Дело в том, что обращение к таблице может выбросить из кэша то, что там было изначально и замедлить таким образом какой-то другой участок кода. Косяк это вы вряд ли найдете быстро, однако подобные чудовищные оптимизации едва ли кому-то понадобятся на практике при реализации обычных программ.

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

С помощью умножения и остатка от деления на степень двойки без единицы можно делать довольно интересные вещи. Обозначим все биты одного байта латинскими буквами от «a» до «h». Число n примет вид: [math]n=a\;b\;c\;d\;e\;f\;g\;h[/math] Умножение [math]n' = n\cdot 10101h[/math] делает «тиражирование» одного байта в трех экземплярах:

+			abcdefgh
		abcdefgh
	abcdefgh
=	abcdefgh	abcdefgh	abcdefgh

Разобьем 24 бита на 8 блоков по 3 бита в каждом (нижеследующая таблица, первая строка). С помощью побитового «и» с маской 249249h (вторая строка таблицы) обнулим в каждом блоке два старших бита.

n⋅10101h		a	b	c	d	e	f	g	h	a	b	c	d	e	f	g	h	a	b	c	d	e	f	g	h
249249h	bin	0	0	1	0	0	1	0	0	1	0	0	1	0	0	1	0	0	1	0	0	1	0	0	1
	hex	2				4				9				2				4				9
n' & 249249h		0	0	c	0	0	f	0	0	a	0	0	d	0	0	g	0	0	b	0	0	e	0	0	h

Третья строка таблицы поясняет шестнадцатеричную запись маски. В последней строке — результат: все биты исходного байта содержаться каждый в своем 3-х битовом блоке, но в ином порядке.
Мы должны сложить эти 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. (Трюк имеет смысл, когда [math]k>1[/math], иначе не совсем понятно как интерпретировать модуль 1). Мы получили сумму блоков по модулю 2^k-1.
От полученного числа нужно взять остаток от деления на 2³-1 (семь) — и получаем сумму наших 8-и блоков по модулю 7. Сумма бит может быть равна 7 или 8, в таком случае алгоритм выдаст 0 и 1 соответственно. В каком случае можем получить 8? Только когда [math]n=255[/math]. В каком случае можем получить 0? Только когда [math]n=0[/math]. Если алгоритм после взятия остатка на 7 даст 0, тогда на входе получили [math]n=0[/math], либо в числе ровно 7 единичных бит. Получаем следующий код:

Код (C):

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

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

Код (C):

1. u8 CountOnes3 (u16 n) {
2.  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⁴-1=15, чтобы сложить получившиеся блоки. Легко подобрать такой множитель: 8040201h. Почему?
Необходимо, чтобы все биты исходного числа заняли правильные позиции в 4-битовых блоках (таблица выше), 8 и 4 не являются взаимно простыми числами, копирование 8 битов 4 раза не даст правильного расположения нужных битов. Придется добавить к байту ноль, то есть тиражировать 9 битов, так как 9 взаимно просто с 4. Получим число, имеющее размер 36 бит, в котором все биты исходного байта стоят на младших позициях 4-битовых блоков. Возьмем побитовое «и» с числом 111111111h, чтобы обнулить по три старших бита в каждом блоке. Далее блоки нужно сложить.

0abc	defg	h0ab	cdef	gh0a	bcde	fgh0	abcd	efgh
0001	0001	0001	0001	0001	0001	0001	0001	0001
000c	000g	000b	000f	000a	000e	0000	000d	000h

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

Код (C):

1. u8 CountOnes3_x64 (u8 n) {
2.  return ((u64)0x08040201*n & 0x111111111) % 15;
3.  }

Недостаток программы — требуется 64-битовая арифметика. Программа задействует 33 бита из 64-х (старшие 3 бита обнуляются).
Какого размера может быть переменная n, чтобы данный трюк правильно работал? Берем остаток от деления на 15, такая переменная не может иметь размер больше 14 бит, иначе придется применить ветвление. Для 14 бит прием работает, если добавить к 14-ти битам один ноль, чтобы все биты встали на свои позиции. Подберем множитель для тиражирования и маску для обнуления ненужных битов.

Код (C):

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

Программа показывает, как мог бы выглядеть код, если бы переменная была размером 14 бит без знака. Этот код будет работать с переменной в 15 бит, при условии, что максимум 14 бит равны единице, либо если [math]n=7FFFh[/math] (этот случай разберем отдельно). Сначала «откусим» младший бит, посчитаем биты в оставшемся 15-ти битовом числе, далее обратно прибавим «откушенный» бит.

Код (C):

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

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

Код (C):

1. u8 CountOnes3_x64 ( u32 n ) {
2.  if (n == 0) return 0;
3.  if (n + 1 == 0) return 32;
4.  u64 res = (n&0xFFF)*0x1001001001001llu & 0x84210842108421llu;
5.  res += ((n&0xFFF000)>>12)*0x1001001001001llu & 0x84210842108421llu;
6.  res += (n>>24)*0x1001001001001llu & 0x84210842108421llu;
7.  res %= 0x1F; if (res == 0) return 31;
8.  return res;
9.  }

Можно вместо трех ветвлений взять 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-битового блока с помощью операций [math]10101h⋅n \& 249249h[/math].

00c	00f	00a	00d	00g	00b	00e	00h
C	F	A	D	G	B	E	H

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

C

F

A

D

G

B

E

H

+​

C

F

A

D

G

B

E

H

+​

C

F

A

D

G

B

E

H

+​

C

F

A

D

G

B

E

H

+​

C

F

A

D

G

B

E

H

+​

C

F

A

D

G

B

E

H

+​

C

F

A

D

G

B

E

H

+

C

F

A

D

G

B

E

H

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

Код (C):

1. u8 CountOnes3_x64_m (u8 n) {
2.   if (n == 0xFF)  return 8;
3.   return ((u64(0x010101*n & 0x249249) * 0x249249) >> 21) & 0x7;
4. }

Взят код предыдущего раздела и в нем заменили взятие остатка от деления на 7 на умножение, сдвиг и побитовое «И». Вместо 3-х ветвлений осталось одно.
Чтобы составить аналогичную программу для 16 бит, нужно взять код предыдущего раздела, в котором взятие остатка от деления на 15 заменяют на умножение.

Код (C):

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

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

Код (C):

1. u8 CountOnes3_x64_m ( u32 n ) {
2.  if (n+1 == 0) return 32;
3.  u64 res = (n&0xFFF)*0x1001001001001llu & 0x84210842108421llu;
4.  res += ((n&0xFFF000)>>12)*0x1001001001001llu & 0x84210842108421llu;
5.  res += (n>>24)*0x1001001001001llu & 0x84210842108421llu;
6.  return (res*0x84210842108421llu >> 55) & 0x1F;
7.  }

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

Удивили результаты для режима x64. Мы обогнали предподсчет с однобайтовой таблицей для случая u32. Можно ли обогнать предподсчет?

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

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

Код (C):

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

Обозначаем биты одного байта первыми латинскими буквами):

n	a b	c d	e f	g h
x=n&55h	0 b	0 d	0 f	0 h
y=(n>>1)&55h	0 a	0 c	0 e	0 g
x+y	a+b	c+d	e+f	g+h

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

Код (C):

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

 

Нижеследующая таблица поясняет результат:

n	a+b	c+d	e+f	g+h
x=n&0x33	0	c+d	0	g+h
y=(n>>2)&0x33	0	a+b	0	e+f
x+y	a+b+c+d		e+f+g+h

Сложим два числа в 4-х битовых полях:

Код (C):

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

n	a+b+c+d	e+f+g+h
x=n&0x0F	0	e+f+g+h
y=(n>>4)&0x0F	0	a+b+c+d
x+y	a+b+c+d+e+f+g+h

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

Код (C):

1. u8 CountOnes4 (u8 n) {
2.  n = ((n>>1) & 0x55) + (n & 0x55);
3.  n = ((n>>2) & 0x33) + (n & 0x33);
4.  n = ((n>>4) & 0x0F) + (n & 0x0F);
5.  return n;
6.  }
7. u8 CountOnes4 (u16 n) {
8.  n = ((n>>1) & 0x5555) + (n & 0x5555);
9.  n = ((n>>2) & 0x3333) + (n & 0x3333);
10.  n = ((n>>4) & 0x0F0F) + (n & 0x0F0F);
11.  n = ((n>>8) & 0x00FF) + (n & 0x00FF);
12.  return n;
13.  }
14. u8 CountOnes4 (u32 n) {
15.  n = ((n>>1) & 0x55555555) + (n & 0x55555555);
16.  n = ((n>>2) & 0x33333333) + (n & 0x33333333);
17.  n = ((n>>4) & 0x0F0F0F0F) + (n & 0x0F0F0F0F);
18.  n = ((n>>8) & 0x00FF00FF) + (n & 0x00FF00FF);
19.  n = ((n>>16) & 0x0000FFFF) + (n & 0x0000FFFF);
20.  return n;
21.  }
22. u8 CountOnes4 (u64 n) {
23.  n = ((n>>1) & 0x5555555555555555llu) + (n & 0x5555555555555555llu);
24.  n = ((n>>2) & 0x3333333333333333llu) + (n & 0x3333333333333333llu);
25.  n = ((n>>4) & 0x0F0F0F0F0F0F0F0Fllu) + (n & 0x0F0F0F0F0F0F0F0Fllu);
26.  n = ((n>>8) & 0x00FF00FF00FF00FFllu) + (n & 0x00FF00FF00FF00FFllu);
27.  n = ((n>>16) & 0x0000FFFF0000FFFFllu) + (n & 0x0000FFFF0000FFFFllu);
28.  n = ((n>>32) & 0x00000000FFFFFFFFllu) + (n & 0x00000000FFFFFFFFllu);
29.  return n;
30. }

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

Код (C):

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

В качестве упражнения предлагается доказать самостоятельно, почему нижеследующий код будет точным отображением предыдущего. Для первой строки дается подсказка: 2-х битовый блок ab имеет точное значение 2a+b, значит вычитание сделает его равным…?

Код (C):

1. u8 CountOnes4_opt (u32 n) {
2.  n -= (n>>1) & 0x55555555;
3.  n = ((n>>2) & 0x33333333 ) + (n & 0x33333333);
4.  n = ((n>>4) + n) & 0x0F0F0F0F;
5.  n = ((n>>8) + n) & 0x00FF00FF;
6.  n = ((n>>16) + n);
7.  return n;
8. }

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

Режим	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 выполним:

Код (C):

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

Число n состоит из 4 байт, которые рассматриваем как 4 числа, сумму которых мы ищем:

n=

A

B

C

D

Можно найти сумму 4-х байт, если умножить число n на 1010101h. Для удобства определения позиции, в которой будет находиться ответ, приводится таблица:

				A	B	C	D
+​			A	B	C	D
+​		A	B	C	D
+	A	B	C	D

Ответ находится в 3-байте (если считать от 0). Комбинированный прием для u16 выглядит так:

Код (C):

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

Он же для u32:

Код (C):

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

Он же для u64:

Код (C):

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

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

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

Читателю предлагается самостоятельно сделать выводы, из двух нижеследующих таблиц.
Итоговое сравнения для режима компиляции x86.

Функция	Тип n
	u8	u16	u32	u64
Наивный метод	38,18	72,00	130,49	384,76
Удаление младшей единички	44,73	55,88	72,02	300,78
Предподсчет 1 байт	0,01	1,83	21,07	36,25
Предподсчет 2 байта	—	0,05	7,95	13,01
Умножение и остаток (32 бита)	12,42	30,57	—	—
Умножение и остаток (64 бита)	39,78	60,48	146,78	—
Умножение и умножение (64 бита)	12,66	42,37	99,90	—
Параллельное суммирование	7,52	14,10	21,12	62,70
Параллельное суммирование (оптимизация)	7,18	11,89	18,86	65,00
Комбинированный метод	—	17,65	13,60	52,65

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

Функция	Тип n
	u8	u16	u32	u64
Наивный метод	37,72	71,51	131,47	227,46
Удаление младшей единички	40,96	69,16	79,13	126,72
Предподсчет 1 байт	0,01	1,44	24,79	26,84
Предподсчет 2 байта	—	0,07	8,49	13,01
Умножение и остаток (32 бита)	13,88	33,88	—	—
Умножение и остаток (64 бита)	6,78	12,28	13,12	—
Умножение и умножение (64 бита)	3,54	4,51	18,35	—
Параллельное суммирование	8,06	11,89	21,30	22,59
Параллельное суммирование (оптимизация)	8,09	10,27	19,20	19,20
Комбинированный метод	—	10,53	13,60	9,41

Замечание

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