Добрый день.

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

В общем, есть массив байтов. Каждый бит в данном массиве соответствует блоку в 16 байт.
Соответственно, если бит == 1, то блок занят, если бит == 0, то блок свободен.
Необходимо найти смещение свободного участка памяти размера n.

Один отсчитывает биты, второй — что найдено.

Здравствуйте, newb, Вы писали:

N>не получается придумать решение, которое меня бы удовлетворило.
То есть решение есть? Что же его не рассказал, чтобы не повторяться?

N>В общем, есть массив байтов. Каждый бит в данном массиве соответствует блоку в 16 байт.
N>Соответственно, если бит == 1, то блок занят, если бит == 0, то блок свободен.
N>Необходимо найти смещение свободного участка памяти размера n.

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

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

Здравствуйте, newb, Вы писали:

N>Добрый день.

N>Понимаю, что задача уровня университетской лабораторной работы, но тем не менее в условиях дедлайна
N>не получается придумать решение, которое меня бы удовлетворило.

N>В общем, есть массив байтов. Каждый бит в данном массиве соответствует блоку в 16 байт.
N>Соответственно, если бит == 1, то блок занят, если бит == 0, то блок свободен.
N>Необходимо найти смещение свободного участка памяти размера n.
Проблему свободно-занято решают списками.

N>>Необходимо найти смещение свободного участка памяти размера n.
B>Проблему свободно-занято решают списками.

У них один бит — одна страница памяти (разреженный массив скорее всего).

Здравствуйте, newb, Вы писали:

N>Понимаю, что задача уровня университетской лабораторной работы, но тем не менее в условиях дедлайна
N>не получается придумать решение, которое меня бы удовлетворило.

N>В общем, есть массив байтов. Каждый бит в данном массиве соответствует блоку в 16 байт.
N>Соответственно, если бит == 1, то блок занят, если бит == 0, то блок свободен.
N>Необходимо найти смещение свободного участка памяти размера n.

Если нужно быстродействие, то я бы завёл массив на 256 элементов с заранее просчитанными значениями и продолжение алгоритма крутил бы уже вокруг этих значений.

Здравствуйте, newb, Вы писали:

N>не получается придумать решение, которое меня бы удовлетворило.

критерии удовлетворения?

N>В общем, есть массив байтов. Каждый бит в данном массиве соответствует блоку в 16 байт.
N>Соответственно, если бит == 1, то блок занят, если бит == 0, то блок свободен.
N>Необходимо найти смещение свободного участка памяти размера n.

Решение в лоб

// обобщённое (требует итераторов по битсету)
template<class It, class Value>
It find_consequent(It begin, It end, int count, Value value)
{
  assert(count > 0);
  int passed = 0;
  It start = begin;
  for(It it = begin; it != end; ++it)
  {
    if(*it != value)
        passed = 0;
    else
    {
        if(passed == 0)
            start = it;
        ++passed;
        if(passed == count)
            return start;
    }
  }
  return end;
}

// то же самое, хардкод, по массиву байтов
int find_consequent_zeros(char* bits, int len, int request)
{
  int start = 0, passed = 0;
  for(int i=0; i!=len; ++i) // побайтово
    for(int j=0; j!=8; ++j) // побитово
      if(bits[i] & (1<<j))
        passed = 0;
      else
      {
        if(!passed) start = i*8+j;
        ++passed;
        if(passed==request) return start;
      }
  return -1;
}

Чтобы ускорить процедуру, можно
— вместо байтов сканировать по uint'ам
— для больших значений request проверять не каждый бит, а байт целиком
— сделать lookup-таблицы для нахождения количества нулевых битов в начале и в конце байта (не факт, что это даст большой прирост к скорости: лишние ветвления, всё такое)