Вроде бы простая задача: посчитать количество единичек в числе.
Я знаю четыре способа её решения: "наивный" метод (пробежаться по всем битам), встроенная в Gcc функция __builtin_popcount, предподсчёт для всех чисел < 0xFFFF и метод за log log X.

Написал тестовую программу (с long long'ами): http://pastebin.com/vTUPkK07
Результаты на Core 2 Duo E4500 2.2 GHz (10^7 long long'ов):
__builtin_popcount: 0.211
countPrecalc: 0.129
countLoglog: 0.269
countSimple: 1.240
Самым быстрым оказался способ с предподсчётом - он делает наивный метод в 10 раз, а метод за loglog и встроенную функцию - в два.
Что любопытно, если попытаться сократить количество операций в предподсчёте (не до 2^16, а до 2^22 - чтобы было 3 сложения вместо четырёх), скорость резко падает до 0.6 - т.е. уже её делают в два раза встроенная функция и loglog.

UPD: при замене int cnt[] на char cnt[] и компиляциис -O2 скорость countPrecalc возврастает в два раза. При компиляции с -O3 - еще в два - до 0.048.