Подсчет числа битов

Опубликовано Sep 30, 2011 в Манипуляция битами | 2 коммент.

, ,

Дано 32-х битное число. Напишите функцию, которая возвращает множество всех 32-х битных чисел, содержащих одинаковое с заданным числом количество ненулевых битов в бинарном представлении. Сигнатуру метода при необходимости можно изменять.

vector needed_numbers(int given_number)
{
  //ваш код
}
1 Цель задания быстрая проверка базовых навыков работы с битовым представлением данных и базовыми контейнерами STL
2 Время выполнения 15 минут для алгоритма прямого перебора
3 Формат выполнения словесное объяснение с использованием бумаги без доступа к документации

Критерии оценки FulcrumWeb:

Кандидат должен продемонстрировать, что умеет работать с целочисленным типом данных в двоичном виде, используя стандартные приемы, например, получение значения конкретного бита числа. Также проверяется способность придумать и реализовать простой алгоритм. В требуемой сигнатуре метода заложено обязательное использование классов из STL. Если работа с STL представляет трудности, то это может быть причиной для изменения сигнатуры метода.

Оценка результатов:

От начинающего программиста ожидается любая реализация, скорее всего основанная на лобовом переборе всех целых чисел и прямом подсчете количества 1 в двоичном представлении числа. При этом мы надеемся не увидеть явного дублирования кода. Например, вычисление количества единиц в числе должно быть оформлено отдельной функцией.

Опытные кандидаты, возможно, предложат более оптимальное решение, основанное, например, на использовании стандартных комбинаторных алгоритмов.