Как определить и работать с массивом битов в C?

Question

Я хочу создать очень большой массив, в котором я пишу 0 и 1. Я пытаюсь смоделировать физический процесс, называемый случайной последовательной адсорбцией, где единицы длины 2, димеры, размещаются на n-мерной решетке в случайном месте, не перекрывая друг друга. Процесс останавливается, когда на решетке больше не остается места для размещения димеров (решетка застряла).

Изначально я начинаю с решетки нулей, а димеры представлены парой единиц. Поскольку каждый димер осажден, сайт слева от димера блокируется из-за того, что димеры не могут перекрываться. Таким образом, я моделирую этот процесс, помещая тройку «1» на решетку. Мне нужно повторить всю симуляцию большое количество раз, а затем определить средний процент покрытия.

Я уже сделал это, используя массив символов для 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;
}

Для реального проекта, который я делаю, он включает в себя не только димеры, но и тримеры, квадримеры и всевозможные формы и размеры (для 2D и 3D).

Я надеялся, что смогу работать с отдельными битами, а не с байтами, но я много читал и, насколько я могу судить, вы можете изменять только 1 байт за раз, так что либо мне нужно сделать какая-то сложная индексация или есть более простой способ сделать это?

Спасибо за ваши ответы

Answer 1

Если я не опаздываю, эта страница дает удивительное объяснение с примерами.

Массив int может использоваться для работы с массивом bits. Предполагая размер int равным 4 bytes, когда мы говорим о int, мы имеем дело с 32 bits. Скажем, у нас есть int A[10], это означает, что мы работаем над 10*4*8 = 320 bits, и на следующем рисунке это показано: (каждый элемент массива имеет 4 больших блока, каждый из которых представляет byte, а каждый из меньших блоков представляет bit )

Итак, чтобы установить k бит в массиве A:

void  SetBit( int A[],  int k )
   {
      int i = k/32;        //gives the corresponding index in the array A
      int pos = k%32;      //gives the corresponding bit position in A[i]

      unsigned int flag = 1;   // flag = 0000.....00001

      flag = flag << pos;      // flag = 0000...010...000   (shifted k positions)

      A[i] = A[i] | flag;      // Set the bit at the k-th position in A[i]
   }

или в сокращенном варианте

void  SetBit( int A[],  int k )
   {
      A[k/32] |= 1 << (k%32);  // Set the bit at the k-th position in A[i]
   }

аналогично очистке k-го бита:

void  ClearBit( int A[],  int k )                
   {
      A[k/32] &= ~(1 << (k%32));
   }

и проверить, если k th бит:

int TestBit( int A[],  int k )
   {
      return ( (A[k/32] & (1 << (k%32) )) != 0 ) ;     
   }

Как сказано выше, эти манипуляции также могут быть записаны как макросы:

#define SetBit(A,k)     ( A[(k/32)] |= (1 << (k%32)) )
#define ClearBit(A,k)   ( A[(k/32)] &= ~(1 << (k%32)) )            
#define TestBit(A,k)    ( A[(k/32)] & (1 << (k%32)) )

Answer 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

Первый из них может быть быстрее на некоторых процессорах или может спасти вас от необходимости возвращаться выполнять операции между одним и тем же битом в нескольких битовых массивах. Это также зеркала установка и очистка битов в поле более тесно, чем вторая реализация. комплект:

my_field[bindex] |= 1<<b;

ясно:

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 - это одна и та же функция, за исключением длинных и длинных длинных соответственно.

Answer 3

Вы можете использовать & (поразрядно и) и << (сдвиг влево). </p>

Например, (1 << 3) приводит к двоичному значению «00001000». Таким образом, ваш код может выглядеть так: </p>

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<bool>, который внутренне определен как вектор битов, в комплекте с прямым индексированием.

Answer 4

bitarray.h

#include <inttypes.h> // defines uint32_t

//typedef unsigned int bitarray_t; // if you know that int is 32 bits
typedef uint32_t bitarray_t;

#define RESERVE_BITS(n) (((n)+0x1f)>>5)
#define DW_INDEX(x) ((x)>>5)
#define BIT_INDEX(x) ((x)&0x1f)
#define getbit(array,index) (((array)[DW_INDEX(index)]>>BIT_INDEX(index))&1)
#define putbit(array, index, bit) \
    ((bit)&1 ?  ((array)[DW_INDEX(index)] |= 1<<BIT_INDEX(index)) \
             :  ((array)[DW_INDEX(index)] &= ~(1<<BIT_INDEX(index))) \
             , 0 \
    )

Использование:

bitarray_t arr[RESERVE_BITS(130)] = {0, 0x12345678,0xabcdef0,0xffff0000,0};
int i = getbit(arr,5);
putbit(arr,6,1);
int x=2;            // the least significant bit is 0
putbit(arr,6,x);    // sets bit 6 to 0 because 2&1 is 0
putbit(arr,6,!!x);  // sets bit 6 to 1 because !!2 is 1

РЕДАКТИРОВАТЬ документы:

"dword" = "double word" = 32-битное значение (без знака, но это не очень важно)

RESERVE_BITS: number_of_bits --> number_of_dwords
    RESERVE_BITS(n) is the number of 32-bit integers enough to store n bits
DW_INDEX: bit_index_in_array --> dword_index_in_array
    DW_INDEX(i) is the index of dword where the i-th bit is stored.
    Both bit and dword indexes start from 0.
BIT_INDEX: bit_index_in_array --> bit_index_in_dword
    If i is the number of some bit in the array, BIT_INDEX(i) is the number
    of that bit in the dword where the bit is stored.
    And the dword is known via DW_INDEX().
getbit: bit_array, bit_index_in_array --> bit_value
putbit: bit_array, bit_index_in_array, bit_value --> 0

getbit(array,i) выбирает двойное слово, содержащее биты i и сдвиги двойное слово вправо , так что бит i становится младшим значащим битом. Затем биты и со значением 1 очищают все остальные биты.

putbit(array, i, v) в первую очередь проверяет младший значащий бит v; если это 0, мы должны очистить бит, и если это 1, мы должны установить его.
Чтобы установить бит, мы делаем побитовое или двойное слово, которое содержит бит, и значение 1 , сдвинутое влево на bit_index_in_dword: этот бит установлен, и другие биты не изменяются .
Чтобы очистить бит, мы делаем побитовое и двойное слово, которое содержит бит и побитовое дополнение из 1 смещено влево на bit_index_in_dword: это значение имеет биты установлены в единицу, кроме единственного нулевого бита в позиции, которую мы хотим очистить.
Макрос заканчивается на , 0, потому что в противном случае он вернул бы значение dword, где хранится бит i, и это значение не имеет смысла. Можно также использовать ((void)0).

Answer 5

Это компромисс:

(1) использовать 1 байт для каждого 2-битного значения - просто, быстро, но использует 4x памяти

(2) упаковывает биты в байты - более сложный, некоторые издержки производительности, использует минимум памяти

Если у вас достаточно памяти, перейдите к (1), в противном случае рассмотрите (2).