C/C++高效位数组

Question

你能推荐有效/干净的方法来操纵任意长度的位数组吗？

现在我使用常规的int/char位掩码,但是当数组长度大于数据类型长度时,这些不是很干净.

std vector<bool> 不适合我.

Answer 1

既然你提到C和C++,我会假设面向C++的解决方案boost::dynamic_bitset可能不适用,而是谈论低级C实现.请注意,如果某些内容boost::dynamic_bitset适用于您,或者您可以找到预先存在的C库,那么使用它们可能比滚动自己更好.

警告:以下代码均未经过测试甚至编译,但它应该非常接近您的需要.

首先,假设您有一个固定的位集大小N.然后类似下面的工作:

typedef uint32_t word_t;
enum { WORD_SIZE = sizeof(word_t) * 8 };

word_t data[N / 32 + 1];

inline int bindex(int b) { return b / WORD_SIZE; }
inline int boffset(int b) { return b % WORD_SIZE; }

void set_bit(int b) { 
    data[bindex(b)] |= 1 << (boffset(b)); 
}
void clear_bit(int b) { 
    data[bindex(b)] &= ~(1 << (boffset(b)));
}
int get_bit(int b) { 
    return data[bindex(b)] & (1 << (boffset(b));
}
void clear_all() { /* set all elements of data to zero */ }
void set_all() { /* set all elements of data to one */ }

如上所述,这有点粗糙,因为它只实现了一个固定大小的单个全局位集.要解决这些问题,您需要从数据结构开始,如下所示:

struct bitset { word_t *words; int nwords; };

然后编写函数来创建和销毁这些位集.

struct bitset *bitset_alloc(int nbits) {
    struct bitset *bitset = malloc(sizeof(*bitset));
    bitset->nwords = (n / WORD_SIZE + 1);
    bitset->words = malloc(sizeof(*bitset->words) * bitset->nwords);
    bitset_clear(bitset);
    return bitset;
}

void bitset_free(struct bitset *bitset) {
    free(bitset->words);
    free(bitset);
}

现在,修改以前的函数来获取struct bitset *参数是相对简单的.仍然无法在其生命周期内重新调整bitset的大小,也没有任何边界检查,但此时也不难添加.

Answer 2

boost::dynamic_bitset 如果长度仅在运行时知道.

std::bitset 如果长度在编译时已知(尽管是任意的).

Answer 3

我写了一个基于Dale Hagglund的响应的工作实现,以提供C(BSD许可证)中的位数组.

https://github.com/noporpoise/BitArray/

请让我知道您的想法/建议.我希望人们在寻找对这个问题的回答时发现它很有用.

Answer 4

这个帖子相当陈旧,但在我的ALFLB库中有一个高效的位阵列套件.

对于许多没有硬件分割操作码的微控制器,该库是高效的,因为它不使用除法:相反,使用屏蔽和位移.(是的,我知道有些编译器会将除以8的转换转换为转换,但这会因编译器而异.)

它已经在最多2 ^ 32-2位(大约40亿位存储在536 MB)中的阵列上进行了测试,但如果在应用程序的for循环中没有使用,则最后2位应该是可访问的.

请参阅下面的doco提取物.Doco是http://alfredo4570.net/src/alflb_doco/alflb.pdf,库是http://alfredo4570.net/src/alflb.zip

享受,
阿尔夫

//------------------------------------------------------------------
BM_DECLARE( arrayName, bitmax);
        Macro to instantiate an array to hold bitmax bits.
//------------------------------------------------------------------
UCHAR *BM_ALLOC( BM_SIZE_T bitmax); 
        mallocs an array (of unsigned char) to hold bitmax bits.
        Returns: NULL if memory could not be allocated.
//------------------------------------------------------------------
void BM_SET( UCHAR *bit_array, BM_SIZE_T bit_index);
        Sets a bit to 1.
//------------------------------------------------------------------
void BM_CLR( UCHAR *bit_array, BM_SIZE_T bit_index);
        Clears a bit to 0.
//------------------------------------------------------------------
int BM_TEST( UCHAR *bit_array, BM_SIZE_T bit_index); 
        Returns: TRUE (1) or FALSE (0) depending on a bit.
//------------------------------------------------------------------
int BM_ANY( UCHAR *bit_array, int value, BM_SIZE_T bitmax); 
        Returns: TRUE (1) if array contains the requested value (i.e. 0 or 1).
//------------------------------------------------------------------
UCHAR *BM_ALL( UCHAR *bit_array, int value, BM_SIZE_T bitmax);
        Sets or clears all elements of a bit array to your value. Typically used after a BM_ALLOC.  
        Returns: Copy of address of bit array
//------------------------------------------------------------------
void BM_ASSIGN( UCHAR *bit_array, int value, BM_SIZE_T bit_index);
        Sets or clears one element of your bit array to your value.
//------------------------------------------------------------------
BM_MAX_BYTES( int bit_max); 
        Utility macro to calculate the number of bytes to store bitmax bits.
        Returns: A number specifying the number of bytes required to hold bitmax bits.
//------------------------------------------------------------------