Честно говоря, одна из реализаций у меня есть, но я ее приведу в следующем сообщении. Может кто-то захочет попробовать реализовать сам, а не срезу смотреть ответ.
Подсчёт количества ненулевых бит в числе v за log2(v) проходов (на примере 8-битного числа):
v = (v & 0x55) + ((v >> 1) & 0x55);
v = (v & 0x33) + ((v >> 2) & 0x33);
return (v & 0x0f) + ((v >> 4) & 0x0f);
Число разбивается на группы бит одной длины (сперва по одному биту). Затем значения соседних пар одновременно складываются и сохраняются в новых группах в два раза большей длины до тех пор, пока не будут сложены половинки числа.
Поскольку длина суммы двух чисел равна длине большего числа с битом для переноса, поэтому для каждой группы в маске групп достаточно иметь единиц не больше номера шага (то есть 1+log2 от длины группы). Hапример, для подсчёта единичных бит в 32-битном числе (с оптимизацией):
#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 >gt; 1) & g21);
v = (v & g22) + ((v >gt; 2) & g22);
v = (v + (v >gt; 4)) & g23;
return (v + (v >gt; 8) + (v >gt; 16) + (v >gt; 24)) & 0x3f;
Для сокращения количества шагов можно суммировать тройки и т.д.:
#define g31 0x49249249ul // = 0100_1001_0010_0100_1001_0010_0100_1001
#define g32 0x381c0e07ul // = 0011_1000_0001_1100_0000_1110_0000_0111
v = (v & g31) + ((v >> 1) & g31) + ((v >> 2) & g31);
v = ((v + (v >> 3)) & g32) + ((v >> 6) & g32);
return (v + (v >> 9) + (v >> 18) + (v >> 27)) & 0x3f;
DAS> Добрый день.
DAS> Интересует реализация такого алгоритма.
DAS> Честно говоря, одна из реализаций у меня есть, но я ее приведу в следующем сообщении. Может кто-то захочет попробовать реализовать сам, а не срезу смотреть ответ.
Можно считать биты не по одному, а по (например) 4
int nbits4[16] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
........
while(......) {
result += nbits4[ x & 0xF ];
x >>= 4;
}
Здравствуйте, DemAS, Вы писали:
DAS> Этот пример я и видел. В связи с чем и возник этот вопрос — а как этот код работает ? Что за магичиские коэффициенты ?
Давай для 8-бит
v = (v & 0x55) + ((v >> 1) & 0x55);
v = (v & 0x33) + ((v >> 2) & 0x33);
return (v & 0x0f) + ((v >> 4) & 0x0f);
число - abcd efgh = 01101011
Разбиваем на группы по 2 бита =>
Первая маска 0101 0101
Проверяем единицы в каждом четном бите (6-4-2-0)
|01|01| |01|01|
&
|ab|cd| |ef|gh|
01 00 00 01
=
b=1 d=0 f=0 h=1 (v & 0x55)
Сдвиг на пол-группы
Проверяем единицы в каждом нечетном бите (7-5-3-1)
|01|01| |01|01|
&
| a|bc| |de|fg|h
=
a=0 c=1 e=1 g=1 (v >> 1) & 0x55
После сложения получим количество единичных битов в каждой группе
Новое значение числа:
|a+b|c+d|e+f|g+h|
1 1 1 2
|01|01| |01|10| v = (v & 0x55) + ((v >> 1) & 0x55);
Теперь разбиваем на группы по 4 бита =>
Вторая маска 0011 0011
аналогично
|0011| |0011|
&
|0101| |0110|
=
0001 0010 (v & 0x33)
и со сдвигом на пол-группы
|0011| |0011|
&
| 01| |0101|10 (v >> 2) & 0x33
=
0001 0001
После сложения получим количество единичных битов в каждой группе
0001 0010
+
0001 0001
=
0010 0011 v = (v & 0x33) + ((v >> 2) & 0x33);
(2 бита в первой иетраде и 3 во второй)
А всего значит 2+3 = 5 установленных битов
0010 + 0011 = 0101 // (v & 0x0f) + ((v >> 4) & 0x0f);
И все!
Эти маски просто разбивает число на группы по сколько-то бит
Здравствуйте, UgN, Вы писали:
UgN>Здравствуйте, DemAS, Вы писали:
DAS>> Этот пример я и видел. В связи с чем и возник этот вопрос — а как этот код работает ? Что за магичиские коэффициенты ?
UgN>Давай для 8-бит
UgN>
UgN> v = (v & 0x55) + ((v >> 1) & 0x55);
UgN> v = (v & 0x33) + ((v >> 2) & 0x33);
UgN> return (v & 0x0f) + ((v >> 4) & 0x0f);
UgN>
Маленькая оптимизация, которая, кстати, используется в решении для 32 бит.
Т.к. в последнем операторе суммарное количество бит не выходит за границу 4-битного числа, т.е. размера текущего блока. Маскировать в последнем операторе можно после выполнения операции:
return (v + (v >> 4)) & 0x0f;
Это же относится к большим размерам блока при большем чем 8 количестве бит в исходном числе.
Для обобщения следует отметить, что переходить к окончательному суммированию надо в тот момент, когда размера текущего блока хватает для сохранения окончательного результата.
Здравствуйте, UgN, Вы писали:
UgN>Здравствуйте, UgN, Вы писали:
UgN>Наверное, все-таки, автор -- Аркадий Белоусов
UgN>Есть ссылки на письмо от 19 сентября 1999 года в эхоконференции fido7.RU.ALGORITHMS.
В выходные книжку посмотрел, где, по моим смутным воспоминанием, была эта задача. Так вот:
Там идет отсылка на 1954 год, с примечанием, что автора указать трудно, но данный алгоритм использовался в одном из первых компьютеров.
DAS> Добрый день.
DAS> Интересует реализация такого алгоритма.
DAS> Честно говоря, одна из реализаций у меня есть, но я ее приведу в следующем сообщении. Может кто-то захочет попробовать реализовать сам, а не срезу смотреть ответ.
Делишь на 2 для получения остатка от деления. Если остаток есть, тогда последний бит 1, если нет, то 0. Сдвигаешь на разряд вправо исходное число, последний бит убирается, и повторяешь деление. Только делить надо не результат деления а результат сдвига. Насколько я помню сдвиг вправо в асме делается командой shr, только не уверен, лет 6 с асмом не работал.