如何定义和使用C中的位数组？

Question

我想创建一个非常大的数组,我在其上写'0'和'1'.我试图模拟一个称为随机顺序吸附的物理过程,其中长度为2的单位二聚体在随机位置沉积在n维晶格上,彼此不重叠.当晶格上没有剩余空间用于沉积更多二聚体(晶格被堵塞)时,该过程停止.

最初我从一个零点开始,二聚体用一对'1'表示.当每个二聚体沉积时,二聚体左侧的位点被阻断,这是因为二聚体不能重叠.因此,我通过在晶格上存储三个'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:

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

现在,bfield_t中的每个long都可以保存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

第一个可能在某些cpus上更快,或者可以节省你需要在多个位阵列中的相同位之间执行操作.它还比第二个实现更密切地反映了现场的设置和清除.组:

my_field[bindex] |= 1<<b;

明确:

my_field[bindex] &= ~(1<<b);

您应该记住,您可以对保存字段的long使用按位运算,这与对各个位的操作相同.

您可能还想查看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.

Answer 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<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"="双字"= 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 的dword并向右移位 dword ,使得位i成为最低有效位.然后,按位和 1清除所有其他位.

putbit(array, i, v)首先检查v的最低有效位; 如果它是0,我们必须清除该位,如果它是1,我们必须设置它.
要设置该位,我们执行按位或包含该位的dword以及由bit_index_in_dword 向左移位的值1 :该位置1 ,其他位不更改.
为了清除该位,我们执行按位和包含该位的dword以及由bit_index_in_dword 向左移位的1 的按位补码:该值将所有位设置为1,除了我们想要清除的位置中的唯一零位. 宏结束,因为否则它将返回存储位i的dword值,并且该值没有意义.人们也可以使用.
, 0((void)0)