Сглаживание Хэкера «Delight» становится намного яснее, когда вы выписываете битовые шаблоны.
unsigned int bitCount(unsigned int x)
{
x = (((x >> 1) & 0b01010101010101010101010101010101)
+ x & 0b01010101010101010101010101010101);
x = (((x >> 2) & 0b00110011001100110011001100110011)
+ x & 0b00110011001100110011001100110011);
x = (((x >> 4) & 0b00001111000011110000111100001111)
+ x & 0b00001111000011110000111100001111);
x = (((x >> 8) & 0b00000000111111110000000011111111)
+ x & 0b00000000111111110000000011111111);
x = (((x >> 16)& 0b00000000000000001111111111111111)
+ x & 0b00000000000000001111111111111111);
return x;
}
Первый шаг добавляет четные биты к нечетным битам, производя сумму бит в каждом двоичном разряде. Другие шаги добавляют куски высокого порядка к кускам младшего порядка, удваивая размер куска до тех пор, пока мы не получим окончательный счет, занимающий весь int.