如何在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个字节，因此要么我需要进行一些复杂的索引，要么就有更简单的方法可以做到？

谢谢你们的答案

- Eddy

---

注意：如果你正在处理单个位，如果效率至关重要，你可能希望在可能的情况下，至少每次对一个字节应用操作（即同时查看多个坐标），因为这样做，如果正确执行，不会额外增加任何成本。除了代码瓶颈部分，这样做可能不值得麻烦。 - Brian

Answer 1

如果我还不算太晚，这个页面提供了非常好的解释和例子。

使用int数组来处理bit数组。假设int大小为4字节，当我们谈论一个int时，我们正在处理32位。假设我们有int A [10]，意味着我们正在处理10×4×8 = 320位，下图展示了它：（数组的每个元素都有4个大块，每个大块代表一个byte，每个小块代表一个bit）

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

// 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]
}

类似于清除k位的方法：

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

测试第k位是否为1：

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

- aniliitb10

---

在决定使用函数还是宏以提高效率时，值得比较编译器生成的机器代码是否有差异（例如，“gcc -O2 -S”）。如果从其他模块调用这些函数，请参见https://dev59.com/s2025IYBdhLWcg3weF2S。如果编译器足够好，在最高优化级别下，函数生成的代码应该等同于宏。坚持使用函数的优点是它们更容易被编辑器、调试器（在较低的优化级别下）和人类理解。 - jwmullally

int的大小取决于编译器，不要假设int为4字节，请进行检查。在一些小型的微控制器中，int可能只有16位。 - quickly_now

在处理位时，使用unsigned int而不是int更有意义；使用sizeof(unsigned)*CHAR_BIT而不是32；或者直接使用uint32_t。如果要支持具有不同int大小的架构，则unsigned int/sizeof(unsigned)可能是一个更好的选择，其中访问32位int需要多于1个指令。 - vgru

是的，我同意，但我只是代表链接中提供的内容，以防该链接不再可访问（实际上，有人请求了该评论，现在该评论已被删除）。 - aniliitb10

在TestBit中，x != 0是必要的吗？它有任何优势吗？ - illiterate

这是上述页面的存档，链接现在无法使用：https://web.archive.org/web/20220706030302/http://www.mathcs.emory.edu/~cheung/Courses/255/Syllabus/1-C-intro/bit-array.html - Cyao

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 位。

您可以通过以下方式计算所需的 big 的索引：

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是同一个函数，除了分别采用长整型和长长整型。

- nategoose

---

一个字节不一定是8位长！从技术上讲，你的bfield_t中的每个long可以容纳CHAR_BIT * sizeof(long)位，而不是8 * sizeof(long)位，只是在许多架构中CHAR_BIT等于8。 - squirl

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>，它在内部定义为位向量，并具有直接索引功能。

- David

---

使用 std::vector<bool> 不会获得最佳性能，因为他最终需要进行两次查找才能获取一对位。是否有足够的理由创建自己的 std::vector<bool> 取决于查找（和赋值）本身是否成为瓶颈。 - Brian

假设C++是一个选项（OP只提到了C），我会毫不犹豫地从std::vector<bool>开始，仅仅为了简洁和可读性。如果我需要更好的性能，我会进行分析以找出瓶颈所在。（这很可能是在rand()而不是向量查找中）。 - David

你可以使用 #define bits(x) BIT##x 代替 char bits[8] = { ... };。 - Chris Lutz

我认为你的意思是使用|=和|，而不是使用&=和&。 - Eddy

我需要创建一个非常大的数组，其中包含超过'int的max_size'个布尔值/位。使用vector<bool>或bitset是否可能？ - Eddy

为了更高效，这取决于架构。有时候移位可能比数组访问更便宜。换句话说，这是一个非常小的“改进”，如果有的话。除非你真的真的需要，否则不要担心它。过早优化是万恶之源。 - Denilson Sá Maia

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的按位补码进行按位与操作：该值除了我们想要清除的位置上的唯一零位之外，所有位都设为1。
宏以, 0结尾，否则会返回存储位i的双字的值，而该值没有意义。也可以使用((void) 0)。

- 18446744073709551615

---

为什么示例中只用了uint32_t，而没有使用uint64_t？ - Dennis V

@DennisV.R. 这段代码很旧了，它是为在32位嵌入式系统上执行实时任务而编写的。由于大多数变量都是int大小（包括指针），因此当你分配1字节时，通常会浪费3字节，所以分配字节没有意义。另一方面，使用32位CPU，64位AND被实现为两个32位AND，因此使用64位ints没有意义。此外，uint64可能需要8字节对齐（这取决于架构和编译器）。因此选择了32位ints。 - 18446744073709551615

@DennisV.R. 顺便说一下，今天我可能会使用 uint_fast32_t 替换 bitarray_t，并将5替换为 DW_INDEX_BITS，它定义为 #define DW_INDEX_BITS (3+__builtin_ctz(sizeof(bitarray_t)))。0x1f 将变为 ((1<<DW_INDEX_BITS)-1)。这种更改后的代码必须经过测试。 __builtin_ctz（）是一个常量表达式（！），但它只适用于GCC。嵌入式系统的板子可能配有相对较旧的编译器（当板子新时，编译器可能是相当新的）。 - 18446744073709551615

@18446744073709551615 在 putbit 中左移的那些位，如果 index 是 31 的话，是否应该转换为 uint32_t？ - Dimitris Fasarakis Hilliard

Answer 5

这是一种权衡：

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

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

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

- Paul R

---

@Paul：不，它使用的内存是原来的4倍，因为他将把2位数字存储在1字节中。然而，根据OP的问题，我认为他已经决定选择（2）。 - Brian

@Brian：谢谢 - 我漏掉了那部分 - 我会相应地更新我的答案。 - Paul R