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

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

, ,

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

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

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

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

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

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

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


2 Коммент. : “Подсчет числа битов”

  1. Глеб says:
     
    #include "stdafx.h"
    #include <bitset>
    #include <vector>
    #include <algorithm>
     
    using std::bitset;
    using std::vector;
     
    //Подсчет числа единичных битов в числе.
    int count(int arg)
    {
    	int mask = 1;
    	int res = 0;
     
    	for(;mask != 0 ; mask <<= 1)
    	{
    		if(mask & arg)
    			res++;
    	}
    	return res;
    }
    //установка значения бита в 1
    inline void set_bit(int &number,int pos)
    {
    	int mask = 1;
    	number = number | (mask <<pos);
    }
    //нерекурсивная функция вычисления количества сочетаний через таблицу биномиальных коэфициентов.
    int combines(int n,int k)
    {
    	int size = sizeof(int)*8 + 1;
    	vector<vector<int>> table(size,0);
    	for(int i=0;i<size;i++)
    		table[i].resize(size,0);
     
    	for(int i=0;i<size;i++)
    	{
    		table[i][i] = 1;
    		table[i][0] = 1;
    	}
     
    	for(int j = 1;j<size;j++)
    	{
    		for(int i = j; i<size; i++)
    		{
    			table[i][j] = table[i-1][j-1] + table[i - 1][j];
    		}
    	}
     
    	return table[n][k];
    }
    //переход к новому сочетанию.
    void next_combine(vector<int>& comb,int n,int k)
    {
    	int i = k - 1;
     
    	while(comb[i] + k - i > n)
    		i--;
    	comb[i]++;
     
    	for(int j = i+1;j < k;j++)
    		comb[j] = comb[j - 1] +1;	
    }
     
    vector<int> needed_numbers(int given_number)
    {
    	int cnt = count(given_number); //кол-во единиц в чисде
    	int n = sizeof(int)*8;//количество битов в числе.
    	int comb = combines(n,cnt);//количество сочетаний.
    	vector<int> numbers;//вектор чисел.
    	vector<int> buf(cnt);//вектор номеров единичных битов.
    	//первое сочетания.
    	for(int i = 0;i < cnt;i++)
    	{
    		buf[i] = i;
    	}
     
    	for(int i = 0;i < comb - 1;i++)
    	{
    		int number = 0;
    		for(int j=0;j < cnt;j++)
    		{//установка значений битов.
    			set_bit(number,buf[j]);
    		}
    		numbers.push_back(number);//запись числа.
    		next_combine(buf,n,cnt);//переход к новому числу.
    	}
    	return numbers;
    }
  2. Решение “в лоб”.

    unsigned CountTrueBits(unsigned n)
    {
    	unsigned numTrueBits = 0;
    	while(n != 0)
    	{
    		if((n & 1) == 1)
    		{
    			numTrueBits++;
    		}
    		n = n >> 1;
    	}
    	return numTrueBits;
    }
    vector<unsigned> needed_numbers(int given_number, unsigned lowerLimit, unsigned UpperLimit)
    {
    	vector<unsigned> answer;
    	unsigned neededNumBits = CountTrueBits(given_number);
    	if(neededNumBits == 0)
    	{
    		return answer;
    	}
    	else
    	{
    		for(int number = lowerLimit; number <= UpperLimit; number++)
    		{
    			if(	(neededNumBits == CountTrueBits(number)) &&
    				(number != given_number))
    			{
    				answer.push_back(number);
    			}
    		}
    		return answer;
    	}
    }

    Хорошо бы конечно просто найти количество возможных перестановок в числе, которое задаёт пользователь. Подумаю об этом на досуге, вспомню математику.

Оставить комментарий

Ваш адрес email не будет опубликован.


*