✅ Решение через смену младшего установленного бита

Ключевая идея этого решения заключается в том, что при побитовом умножении чисел n и n - 1 младший установленный бит числа n всегда сменяется на 0. При этом все остальные биты остаются неизменными.

Вместо проверки каждого бита числа мы неоднократно обращаем наименее значимый единичный бит числа на 0 и добавляем 1 к нашему счетчику. При этом число n мы заменяем на полученный результат побитового умножения.

Как только число n становится равным 0, мы знаем, что в нем больше не осталось единиц. Это означает, что в нашем счетчике count содержится правильное количество единиц, которые были в битовом представлении числа n.

Посмотреть реализацию в блоге.

🅾️ Оценка сложности

По времени

В худшем случае все биты n являются единичными и мы имеем максимум 32 бита. Из-за фиксированного количество итераций можно считать сложность константной, то есть — O(1).

По памяти

O(1) — дополнительная память константна.

#bit_manipulation #easy