C/C++ 高效位数组

C/C++ efficient bit array

提问by Anycorn

Can you recommend efficient/clean way to manipulate arbitrary length bit array?

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

Right now I am using regular int/char bitmask, but those are not very clean when array length is greater than datatype length.

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

std vector<bool>is not available for me.

std vector<bool>对我不可用。

采纳答案by kennytm

boost::dynamic_bitsetif the length is only known in run time.

boost::dynamic_bitset如果长度仅在运行时已知。

std::bitsetif the length is known in compile time (although arbitrary).

std::bitset如果长度在编译时已知（尽管是任意的）。

回答by Dale Hagglund

Since you mention C as well as C++, I'll assume that a C++-oriented solution like boost::dynamic_bitsetmight not be applicable, and talk about a low-level C implementation instead. Note that if something like boost::dynamic_bitsetworks for you, or there's a pre-existing C library you can find, then using them can be better than rolling your own.

由于您提到 C 和 C++，我将假设面向 C++ 的解决方案boost::dynamic_bitset可能不适用，而是讨论低级 C 实现。请注意，如果类似的东西boost::dynamic_bitset适合您，或者您可以找到预先存在的 C 库，那么使用它们可能比滚动您自己的库更好。

Warning: None of the following code has been tested or even compiled, but it should be very close to what you'd need.

警告：以下代码都没有经过测试甚至编译，但它应该非常接近您的需要。

To start, assume you have a fixed bitset size N. Then something like the following works:

首先，假设您有一个固定的位集大小 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 */ }

As written, this is a bit crude since it implements only a single global bitset with a fixed size. To address these problems, you want to start with a data struture something like the following:

正如所写，这有点粗糙，因为它仅实现了一个具有固定大小的全局位集。为了解决这些问题，您需要从类似于以下的数据结构开始：

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

and then write functions to create and destroy these bitsets.

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

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

Now, it's relatively straightforward to modify the previous functions to take a struct bitset *parameter. There's still no way to re-size a bitset during its lifetime, nor is there any bounds checking, but neither would be hard to add at this point.

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

回答by Isaac Turner

I've written a working implementation based off Dale Hagglund's responseto provide a bit array in C (BSD license).

我已经根据Dale Hagglund 的响应编写了一个工作实现，以提供 C 中的位数组（BSD 许可证）。

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

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

Please let me know what you think / give suggestions. I hope people looking for a response to this question find it useful.

请让我知道您的想法/提出建议。我希望寻找这个问题的答案的人会发现它有用。

回答by alf

This posting is rather old, but there is an efficient bit array suite in C in my ALFLB library.

这篇文章相当陈旧，但在我的 ALFLB 库中有一个高效的 C 位数组套件。

For many microcontrollers without a hardware-division opcode, this library is EFFICIENT because it doesn't use division: instead, masking and bit-shifting are used. (Yes, I know some compilers will convert division by 8 to a shift, but this varies from compiler to compiler.)

对于许多没有硬件除法操作码的微控制器，这个库是有效的，因为它不使用除法：相反，使用了屏蔽和位移位。（是的，我知道有些编译器会将除以 8 转换为移位，但这因编译器而异。）

It has been tested on arrays up to 2^32-2 bits (about 4 billion bits stored in 536 MBytes), although last 2 bits should be accessible if not used in a for-loop in your application.

它已经在最多 2^32-2 位（大约 40 亿位存储在 536 兆字节中）的数组上进行了测试，尽管最后 2 位如果不在应用程序的 for 循环中使用，则应该可以访问。

See below for an extract from the doco. Doco is http://alfredo4570.net/src/alflb_doco/alflb.pdf, library is http://alfredo4570.net/src/alflb.zip

请参阅下面的 doco 摘录。Doco 是http://alfredo4570.net/src/alflb_doco/alflb.pdf，库是http://alfredo4570.net/src/alflb.zip

Enjoy,
Alf

享受，
阿尔夫

//------------------------------------------------------------------
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.
//------------------------------------------------------------------

回答by Brian R. Bondy

You can use std::bitset

您可以使用std::bitset

int main() {
  const bitset<12> mask(2730ul); 
  cout << "mask =      " << mask << endl;

  bitset<12> x;

  cout << "Enter a 12-bit bitset in binary: " << flush;
  if (cin >> x) {
    cout << "x =        " << x << endl;
    cout << "As ulong:  " << x.to_ulong() << endl;
    cout << "And with mask: " << (x & mask) << endl;
    cout << "Or with mask:  " << (x | mask) << endl;
  }
}

回答by Samwhoo

I know it's an old post but I came here to find a simple C bitset implementation and none of the answers quite matched what I was looking for, so I implemented my own based on Dale Hagglund's answer. Here it is :)

我知道这是一篇旧帖子，但我来这里是为了找到一个简单的 C bitset 实现，但没有一个答案与我想要的完全匹配，所以我根据 Dale Hagglund 的答案实现了我自己的。这里是 ：）

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

typedef uint32_t word_t;
enum { BITS_PER_WORD = 32 };
struct bitv { word_t *words; int nwords; int nbits; };

struct bitv* bitv_alloc(int bits) {
    struct bitv *b = malloc(sizeof(struct bitv));

    if (b == NULL) {
        fprintf(stderr, "Failed to alloc bitv\n");
        exit(1);
    }

    b->nwords = (bits >> 5) + 1;
    b->nbits  = bits;
    b->words  = malloc(sizeof(*b->words) * b->nwords);

    if (b->words == NULL) {
        fprintf(stderr, "Failed to alloc bitv->words\n");
        exit(1);
    }

    memset(b->words, 0, sizeof(*b->words) * b->nwords);

    return b;
}

static inline void check_bounds(struct bitv *b, int bit) {
    if (b->nbits < bit) {
        fprintf(stderr, "Attempted to access a bit out of range\n");
        exit(1);
    }
}

void bitv_set(struct bitv *b, int bit) {
    check_bounds(b, bit);
    b->words[bit >> 5] |= 1 << (bit % BITS_PER_WORD);
}

void bitv_clear(struct bitv *b, int bit) {
    check_bounds(b, bit);
    b->words[bit >> 5] &= ~(1 << (bit % BITS_PER_WORD));
}

int bitv_test(struct bitv *b, int bit) {
    check_bounds(b, bit);
    return b->words[bit >> 5] & (1 << (bit % BITS_PER_WORD));
}

void bitv_free(struct bitv *b) {
    if (b != NULL) {
        if (b->words != NULL) free(b->words);
        free(b);
    }
}

void bitv_dump(struct bitv *b) {
    if (b == NULL) return;

    for(int i = 0; i < b->nwords; i++) {
        word_t w = b->words[i];

        for (int j = 0; j < BITS_PER_WORD; j++) {
            printf("%d", w & 1);
            w >>= 1;
        }

        printf(" ");
    }

    printf("\n");
}

void test(struct bitv *b, int bit) {
    if (bitv_test(b, bit)) printf("Bit %d is set!\n", bit);
    else                   printf("Bit %d is not set!\n", bit);
}

int main(int argc, char *argv[]) {
    struct bitv *b = bitv_alloc(32);

    bitv_set(b, 1);
    bitv_set(b, 3);
    bitv_set(b, 5);
    bitv_set(b, 7);
    bitv_set(b, 9);
    bitv_set(b, 32);
    bitv_dump(b);
    bitv_free(b);

    return 0;
}

回答by Roel911

I use this one:

我用这个：

//#include <bitset>
#include <iostream>
//source http://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit-in-c
#define BIT_SET(a,b) ((a) |= (1<<(b)))
#define BIT_CLEAR(a,b) ((a) &= ~(1<<(b)))
#define BIT_FLIP(a,b) ((a) ^= (1<<(b)))
#define BIT_CHECK(a,b) ((a) & (1<<(b)))

/* x=target variable, y=mask */
#define BITMASK_SET(x,y) ((x) |= (y))
#define BITMASK_CLEAR(x,y) ((x) &= (~(y)))
#define BITMASK_FLIP(x,y) ((x) ^= (y))
#define BITMASK_CHECK(x,y) ((x) & (y))

回答by chesslover

I have recently released BITSCAN, a C++ bit string library which is specifically oriented towards fast bit scanning operations. BITSCAN is available here. It is in alpha but still pretty well tested since I have used it in recent years for research in combinatorial optimization (e.g. in BBMC, a state of the art exact maximum clique algorithm). A comparison with other well known C++ implementations (STL or BOOST) may be found here.

我最近发布了 BITSCAN，这是一个 C++ 位字符串库，专门面向快速位扫描操作。BITSCAN在这里可用。它处于 alpha 阶段，但仍然经过很好的测试，因为我近年来将它用于组合优化的研究（例如，在BBMC 中，一种最先进的精确最大集团算法）。可以在此处找到与其他众所周知的 C++ 实现（STL 或 BOOST）的比较。

I hope you find it useful. Any feedback is welcome.

希望对你有帮助。欢迎任何反馈。

回答by Danh Hoang

In micro controller development, some times we need to use 2-dimentional array (matrix) with element value of [0, 1] only. That means if we use 1 byte for element type, it wastes the memory greatly (memory of micro controller is very limited). The proposed solution is that we should use 1 bit matrix (element type is 1 bit).

在微控制器开发中，有时我们只需要使用元素值为[0, 1]的二维数组（矩阵）。这意味着如果我们使用 1 个字节作为元素类型，则会极大地浪费内存（微控制器的内存非常有限）。建议的解决方案是我们应该使用 1 位矩阵（元素类型为 1 位）。

http://htvdanh.blogspot.com/2016/09/one-bit-matrix-for-cc-programming.html

http://htvdanh.blogspot.com/2016/09/one-bit-matrix-for-cc-programming.html

回答by EddyXorb

I recently implemented a small header-only library called BitContainer just for this purpose. It focuses on expressiveness and compiletime abilities and can be found here: https://github.com/EddyXorb/BitContainer

为此，我最近实现了一个名为 BitContainer 的仅包含头文件的小型库。它侧重于表现力和编译时能力，可以在这里找到：https: //github.com/EddyXorb/BitContainer

It is for sure not the classical way to look at bitarrays but can come in handy for strong-typing purposes and memory efficient representation of named properties.

它肯定不是查看位数组的经典方法，但可以用于强类型目的和命名属性的内存高效表示。

Example:

例子：

constexpr Props props(Prop::isHigh(),Prop::isLow()); // intialize BitContainer of type Props with strong-type Prop

constexpr bool result1 = props.contains(Prop::isTiny()) // false
constexpr bool result2 = props.contains(Prop::isLow())  // true