Как определить 2-битные числа в C, если это возможно?

Question

Для моего университетского процесса я моделирую процесс, называемый случайной последовательной адсорбцией.Одна из вещей, которую я должен сделать, заключается в случайном размещении квадратов (которые не могут перекрываться) на решетке до тех пор, пока не останется свободного места, повторяя процесс несколько раз, чтобы найти средний% покрытия «заклинивания».

В основном я выполняю операции с большим массивом целых чисел, из которых существует 3 возможных значения: 0, 1 и 2. Сайты, отмеченные '0', пусты, сайты, отмеченные '1', являютсяполный.Первоначально массив определяется следующим образом:

int i, j;
int n = 1000000000;
int array[n][n];

for(j = 0; j < n; j++)
{
    for(i = 0; i < n; i++)
    {
        array[i][j] = 0;
    }
}

Скажем, я хочу разместить 5 * 5 квадратов случайным образом на массиве (который не может перекрываться), чтобы квадраты были представлены '1'.Это можно сделать, выбрав координаты x и y случайным образом, а затем создав квадрат 5 * 5 из «1» с точкой поворота квадрата, начинающейся в этой точке.Затем я бы пометил места возле площади как «2».Они представляют сайты, которые недоступны, поскольку размещение квадрата на этих сайтах может привести к тому, что он будет перекрывать существующий квадрат.Этот процесс будет продолжаться до тех пор, пока не останется места для размещения квадратов в массиве (в основном, в массиве не останется нулей)

В любом случае, до точки.Я хотел бы сделать этот процесс максимально эффективным, используя побитовые операции.Это было бы легко, если бы мне не нужно было отмечать участки возле площадей.Мне было интересно, возможно ли создание 2-битного числа, чтобы я мог учесть сайты, отмеченные знаком «2».

Извините, если это звучит действительно сложно, я просто хотел объяснить, почему я хочу это сделать.

Answer 1

Невозможно создать тип данных размером 2 бита, поскольку он не будет адресуемым. Что вы можете сделать, это упаковать несколько 2-битных чисел в большую ячейку:

   struct Cell {
      a : 2;
      b : 2;
      c : 2;
      d : 2;
   };

Указывает, что каждый из членов a, b, c и d должен занимать два бита в памяти.

РЕДАКТИРОВАТЬ: Это всего лишь пример того, как создавать 2-битные переменные, для рассматриваемой проблемы наиболее эффективной реализацией, вероятно, будет создание массива int и завершение немного возиться с парой set / get методов.

Answer 2

Вместо двухбитного массива вы можете использовать два отдельных 1-битных массива. Один содержит заполненные квадраты, а другой - соседние (или доступные квадраты, если это более эффективно).

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

Answer 3

Основная идея

К сожалению, в C. нет способа сделать это. Вы можете создавать массивы из 1 байта, 2 байта и т. Д., Но вы не можете создавать области битов.

Лучшее, что вы можете сделать, это написать новую библиотеку для себя, которая выглядит так, как будто вы имеете дело с массивами из 2 битов, но на самом деле выполняет много тяжелой работы. Точно так же, как строковые библиотеки дают вам функции, которые работают с «строками» (которые в C являются просто массивами), вы будете создавать новую библиотеку, которая работает с «битовыми массивами» (которые в действительности будут массивами целых чисел, с несколькими специальными функциями для работы с ними, как если бы они были массивами битов.

ПРИМЕЧАНИЕ. Если вы новичок в C и не изучили идеи «создания новой библиотеки / модуля» или концепцию «абстракции», то я бы рекомендовал ознакомиться с ними, прежде чем продолжить этот проект. Понимание их важнее IMO, чем оптимизация вашей программы, чтобы она занимала немного меньше места.

Как реализовать эту новую "библиотеку" или модуль

Для ваших нужд я бы создал новый модуль под названием «2-битный массив», который будет экспортировать функции для работы с 2-битными массивами по мере необходимости.

В нем будет несколько функций, которые имеют дело с установкой / чтением битов, так что вы можете работать с ним, как если бы у вас был настоящий массив битов (у вас фактически будет массив целых чисел или что-то еще, но модуль будет сделать так, чтобы у вас был массив битов).

При использовании этого модуля хотелось бы что-то вроде этого:

// This is just an example of how to use the functions in the twoBitArray library.
twoB my_array = Create2BitArray(size); // This will "create" a twoBitArray and return it.
SetBit(twoB, 5, 1); // Set bit 5 to 1 // 
bit b = GetBit(twoB, 5); // Where bit is typedefed to an int by your module.

Что модуль фактически сделает, так это реализует все эти функции, используя обычные старые массивы целых чисел.

Например, функция GetBit() для GetBit(my_arr, 17) вычислит, что это 1-й бит в 4-м целом числе вашего массива (очевидно, в зависимости от sizeof(int)), и вы вернете его с помощью побитового операции.

Answer 4

Вы можете сжать одно измерение массива в целочисленные ячейки.Чтобы преобразовать координату (скажем, например, x) в позицию внутри байта:

byte cell = array[i][ x / 4 ];
byte mask = 0x0004 << (x % 4);
byte data = (cell & mask) >> (x % 4);

для записи данных сделайте обратное