В общем случае проблема описана в "Алгоритмических трюках для программистов" Г. Уоррена. По ссылке (другой источник, но есть в онлайне) много деталей, практически же код выглядит так: https://graphics.stanford.edu/~seander/bithacks.html
v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
Что микрософт компилирует такое (
https://godbolt.org/z/hC84ov -- во что gcc не знаю, сломался):
lsrs r3,r0,#1
bic r3,r3,#0xAAAAAAAA
subs r1,r0,r3
lsrs r3,r1,#2
bic r2,r3,#0xCCCCCCCC
bic r3,r1,#0xCCCCCCCC
add r3,r3,r2
add r3,r3,r3,lsr #4
bic r2,r3,#0xF0F0F0F0
mvn r3,#0xFEFEFEFE
mul r3,r2,r3
lsrs r0,r3,#0x18
Что составляет 12 команд. Что сильно меньше, чем 100500. Такие вещи вообще обычно реализованы в функциях libgcc и написаны руками на ассемблере для конкретных архитектур, но в данном случае на C есть типовая для всех архитектур реализация:
https://code.woboq …gcc/libgcc2.c.html#841 (табличный способ используется только для всяких AVR'ов и RL78, не 32-битных машин).
Кому сильно надо быстро пишут руками и под конкретную архитектуру, только эти кому сильно надо обычно сильны только в изучении отдельных ассемблерных команд отдельного процессора и тыкания ими всех налево и направо, и даже не понимают, что в общем объёме кода посчитать биты, даже если это алгоритм им. АОНа, обычно далеко не самое важное.
Ссылка на Hackers Delight (
https://www.hackersdelight.org/) по-русски "Алгоритмические трюки".