Одна из классических задач в программировании (по крайней мере, о способах ее решения упоминает Дональд Кнут в своем классическом труде) – подсчет выставленных в “1″ бит в числе.
Зачем?
Почему эта задача важна? Во-первых, она интересна сама по себе – есть несколько способов решения, которые кардинально отличаются производительностью и выбор правильной реализации может значительно ускорить ваш код. Во-вторых, у нее много практических применений – например, в протоколах маршрутизации или поиска. И, в-третьих, она встречается на собеседованиях в крупных компаниях, так что будет не лишним немного освежить свои знания.
Поиск в сети даст достаточно подробностей, здесь же я хочу привести краткую сводку фактов.
Методы подсчета можно условно разделить на три области – shifting, algebraic logic и table lookup.
