50

我想创建一个非常大的数组，在上面写 '0' 和 '1'。我正在尝试模拟一种称为随机顺序吸附的物理过程，其中长度为 2 的单位（二聚体）被沉积在随机位置的 n 维晶格上，而不会相互重叠。当晶格上没有更多空间用于沉积更多二聚体（晶格被堵塞）时，该过程停止。

最初，我从零格开始，二聚体由一对“1”表示。随着每个二聚体的沉积，二聚体左侧的位点被阻塞，因为二聚体不能重叠。所以我通过在格子上放置三个'1'来模拟这个过程。我需要多次重复整个模拟，然后计算出平均覆盖率。

我已经使用 1D 和 2D 晶格的字符数组完成了这项工作。目前，在处理 3D 问题和更复杂的概括之前，我正在尝试使代码尽可能高效。

这基本上是代码在一维中的样子，简化：

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 个字节，所以要么我需要做一些复杂的索引或者有更简单的方法吗？

感谢您的回答

4

5 回答 5

56

如果我还不算太晚，这个页面会用例子给出很棒的解释。

一个数组int可以用来处理数组bits。假设大小为int，4 bytes当我们谈论 an 时int，我们正在处理32 bits. 假设我们有int A[10]，表示我们正在处理10*4*8 = 320 bits，下图显示了它：（数组的每个元素有 4 个大块，每个块代表 a byte，每个较小的块代表 a bit）

在此处输入图像描述

因此，要设置k数组中的第 th 位A：

// NOTE: if using "uint8_t A[]" instead of "int A[]" then divide by 8, not 32
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]
}

类似于清除kth 位：

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 ) ;     
}

如上所述，这些操作也可以写成宏：

// Due order of operation wrap 'k' in parentheses in case it
// is passed as an equation, e.g. i + 1, otherwise the first
// part evaluates to "A[i + (1/32)]" not "A[(i + 1)/32]"
#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)) )
于 2015-06-02T08:11:47.030 回答
11 
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

第一个在某些 cpu 上可能更快，或者可以节省您在多个位数组中的同一位之间执行操作的转移。它还比第二个实现更接近地反映了字段中位的设置和清除。放：

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。

于 2010-03-26T19:52:32.690 回答
7

您可以使用 &（按位与）和 <<（左移）。

例如，(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>内部定义为位向量的一个，并带有直接索引。

于 2010-03-26T17:34:10.793 回答
6

位数组.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的dword 并将 dword右移，以便位 i 成为最低有效位。然后，按位加 1 清除所有其他位。

putbit(array, i, v)首先检查 v 的最低有效位；如果为 0，我们必须清除该位，如果为 1，我们必须设置它。
要设置该位，我们对包含该位的 dword进行按位或运算，并将 1 的值左移bit_index_in_dword：该位已设置，其他位不变。
要清除该位，我们对包含该位和 1 的按位补码的 dword 进行按位与运算，左移bit_index_in_dword：该值将所有位设置为 1，除了我们要清除的位置中唯一的零位。
宏以, 0因为否则它将返回存储位 i 的 dword 的值，并且该值没有意义。也可以使用((void)0).

于 2014-07-15T08:20:24.483 回答
2

这是一个权衡：

(1) 每个 2 位值使用 1 个字节 - 简单、快速，但使用 4x 内存

(2) 将位打包成字节 - 更复杂，一些性能开销，使用最少的内存

如果您有足够的可用内存，则选择（1），否则考虑（2）。

于 2010-03-26T17:35:31.137 回答