Один из алгоритмов подсчёта единичных битов в числах от 1 до n: 1

1. Найти наибольшую степень двойки t=2k, не превосходящую данное число, и по формуле получить число битов до неё. 1
2. Оставшиеся числа (p=n-t+1 штук) обработать рекурсивно, учитывая p старших единиц. 1

Сложность такого подхода — логарифмическая O(log(n)). 1 Расчёт будет мгновенным для очень больших чисел. 1

Ещё один алгоритм для подсчёта количества единиц в битовом представлении символов строки: 3

1. Разделить исходное значение на пары смежных бит, вычислить сумму в пределах каждой пары и поместить её на место самой пары. 3
2. Поступить аналогичным образом с только что полученными значениями, увеличив длины битовых полей вдвое. 3
3. Повторять предыдущий шаг, пока не достигнем исходной битовой длины значения. 3

Также для подсчёта количества битов в длинном десятичном целом числе, представленном в виде строки, можно использовать весовой алгоритм Хэмминга. 2