Как определить и работать с массивом битов в C?
Я хочу создать очень большой массив, на котором я пишу '0 и '1's. Я пытаюсь моделировать физический процесс, названный случайной последовательной адсорбцией, где единицы длины 2, димеры, депонированы на n-мерную решетку в случайном местоположении, не перекрывая друг друга. Процесс останавливается, когда больше нет комнаты, покинутой на решетке для внесения большего количества димеров (решетка создана затор).
Первоначально я запускаю с решетки, обнуляет, и димеры представлены парой '1's. Поскольку каждый димер депонирован, сайт слева от димера заблокирован, вследствие того, что димеры не могут наложиться. Таким образом, я моделирую этот процесс путем внесения тройного из '1's на решетке. Я должен повторить все моделирование большое количество раз и затем разработать средний % покрытия.
Я уже сделал это использование массива символов для 1D и 2D решетки. В данный момент я пытаюсь сделать код максимально эффективным, прежде, чем работать над 3D проблемой и более сложными обобщениями.
Это в основном, на что код похож в 1D, упрощенный:
int main()
{
/* Define lattice */
array = (char*)malloc(N * sizeof(char));
total_c = 0;
/* Carry out RSA multiple times */
for (i = 0; i < 1000; i++)
rand_seq_ads();
/* Calculate average coverage efficiency at jamming */
printf("coverage efficiency = %lf", total_c/1000);
return 0;
}
void rand_seq_ads()
{
/* Initialise array, initial conditions */
memset(a, 0, N * sizeof(char));
available_sites = N;
count = 0;
/* While the lattice still has enough room... */
while(available_sites != 0)
{
/* Generate random site location */
x = rand();
/* Deposit dimer (if site is available) */
if(array[x] == 0)
{
array[x] = 1;
array[x+1] = 1;
count += 1;
available_sites += -2;
}
/* Mark site left of dimer as unavailable (if its empty) */
if(array[x-1] == 0)
{
array[x-1] = 1;
available_sites += -1;
}
}
/* Calculate coverage %, and add to total */
c = count/N
total_c += c;
}
Для фактического проекта я делаю, он включает не только димеры, но и тримеры, quadrimers, и все виды форм и размеров (для 2D и 3D).
Я надеялся, что смогу работать с отдельными битами вместо байтов, но я читал вокруг и насколько я могу сказать, что можно только измениться на 1 байт за один раз, таким образом, или я должен сделать некоторую сложную индексацию или существует более простой способ сделать это?
Спасибо за Ваши ответы
3 ответа
Вы можете использовать & (побитовое и) и << (сдвиг влево).
Например, (1 << 3) приводит к "00001000" в двоичном формате. Итак, ваш код может выглядеть так:
char eightBits = 0;
//Set the 5th and 6th bits from the right to 1
eightBits &= (1 << 4);
eightBits &= (1 << 5);
//eightBits now looks like "00110000".
Затем просто увеличьте его с помощью массива символов и определите соответствующий байт для изменения в первую очередь.
Для большей эффективности вы можете заранее определить список битовых полей и поместить их в массив:
#define BIT8 0x01
#define BIT7 0x02
#define BIT6 0x04
#define BIT5 0x08
#define BIT4 0x10
#define BIT3 0x20
#define BIT2 0x40
#define BIT1 0x80
char bits[8] = {BIT1, BIT2, BIT3, BIT4, BIT5, BIT6, BIT7, BIT8};
Тогда вы избежите накладных расходов на сдвиг битов и сможете индексировать свои биты, превратив предыдущий код в:
eightBits &= (bits[3] & bits[4]);
В качестве альтернативы, если вы можете использовать C ++, вы можете просто использовать std :: vector , который внутренне определен как вектор битов с прямой индексацией.
Это сделка- выкл:
(1) использовать 1 байт для каждого 2-битного значения - просто, быстро, но использует 4-кратную память
(2) упаковать биты в байты - более сложный, некоторые накладные расходы на производительность, использует минимум памяти
Если у вас достаточно памяти, тогда выберите (1), в противном случае рассмотрите (2).
typedef unsigned long bfield_t[ size_needed/sizeof(long) ];
// long because that's probably what your cpu is best at
// The size_needed should be evenly divisable by sizeof(long) or
// you could (sizeof(long)-1+size_needed)/sizeof(long) to force it to round up
Теперь каждый long в bfield_t может содержать sizeof (long) * 8 бит.
Вы можете вычислить индекс необходимого большого числа по:
bindex = index / (8 * sizeof(long) );
и номер вашего бита по
b = index % (8 * sizeof(long) );
. Затем вы можете найти нужное вам число и затем замаскировать из него нужный бит.
result = my_field[bindex] & (1<<b);
или
result = 1 & (my_field[bindex]>>b); // if you prefer them to be in bit0
Первый может быть быстрее на некоторых процессорах или может избавить вас от необходимости сдвигать назад из-за необходимости выполнять операции между одним и тем же битом в нескольких битовых массивах. Он также более точно отражает настройку и очистку бита в поле, чем вторая реализация. set:
my_field[bindex] |= 1<<b;
clear:
my_field[bindex] &= ~(1<<b);
Вы должны помнить, что вы можете использовать побитовые операции с длинные числа, содержащие поля , и это то же самое, что и операции с отдельными битами.
Вы, вероятно, также захотите изучить функции ffs, fls, ffc и flc, если они доступны. ffs всегда должен быть доступен в strings.h . Он существует только для этой цели - строка битов.
В любом случае, он устанавливается первым и по сути:
int ffs(int x) {
int c = 0;
while (!(x&1) ) {
c++;
x>>=1;
}
return c; // except that it handles x = 0 differently
}
Это обычная операция для процессоров, для которых есть инструкция, и ваш компилятор, вероятно, сгенерирует ее. инструкцию, а не вызывать функцию, подобную той, которую я написал. На x86, кстати, есть инструкция. О, и ffsl и ffsll - это одна и та же функция, за исключением того, что они занимают long и long long соответственно.