Нужен НЕТРИВИАЛЬНЫЙ алгоритм для нахождения веса булева вектора.

Вес булева вектора - количество единичек в нём.

Тривиальный алгоритм (последовательно просматривать каждый бит) имеет вычислительную сложность, прямо пропорциональную n (n - кол-во всех бит в векторе, "разрядность" всего вектора).

Нужен нетривиальный.

(И он был, просто я вспомнить никак не могу, а лекции выкинул. Там вроде весь вектор делился пополам, затем каждая половинка, и т.д.. Вроде, рекурсивный он был. И вычислительная сложность его, была пропорциональна, может, log(n), но точно не n (а иначе, нафиг бы он был тогда нужен)).

Плз, хэлп! Ссылочку, или идею хоть бы.

Добавлено через 7 часов 42 минуты 35 секунд

Точно, нашёл, что есть такой, сложности именно O(log2(n)).

Только сам алгоритм - не могу найти нигде.