你能推荐一个高效/清晰的方法来操作任意长度的位数组吗？
现在我正在使用常规的int/char位掩码，但当数组长度大于数据类型长度时，它们并不是很清晰。
std vector<bool> 对我不可用。
10个回答
50
由于您提到了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 */ }
按照原文的说法，这段代码有些粗糙，因为它只实现了一个固定大小的单一全局bitset。为解决这些问题，您需要从以下类似的数据结构开始：
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的大小，也没有边界检查，但是在这个阶段添加它们都不难。
- Dale Hagglund
1
3为了改进这个答案，我会使用CHAR_BIT (limits.h)代替8。你可能在一个字节不是8位的架构上。 - Luke Skywalker
21
boost::dynamic_bitset 适用于长度在运行时才知道的情况。
std::bitset 适用于长度在编译时已知的情况（尽管是任意长度）。
- kennytm
3
谢谢。我不能直接使用（GPU 设备），但我可以查看源代码。 - Anycorn
@aaa：假设设备的位数小于32位，您可以使用
.to_ulong()来获取设备的数字值。 - kennytm运行时函数需要特定的关键字，因此我不能直接在那个意义上使用位集。 - Anycorn
14
我基于Dale Hagglund的回答编写了一个可用的实现，提供了C中的位数组（BSD许可证）。
https://github.com/noporpoise/BitArray/
请告诉我您的想法/提供建议。我希望寻找问题答案的人会发现它有用。
- Isaac Turner
3
1谢谢！你帮我省了几个小时的编程时间。我会检查你的代码，等待我的评论 ;) - diegocaro
它似乎假定了一个小端处理器，并在大端处理器上失败。 - JonS
@JonS，请在GitHub上开一个问题指定哪些测试失败 - 它应该支持大端机器。不幸的是，我没有一个来测试。 - Isaac Turner
7
这篇文章有些旧了，但是我在我的ALFLB库中有一个高效的C位数组套件。
对于许多没有硬件除法操作码的微控制器来说，这个库是高效的，因为它不使用除法：而是使用掩码和位移。(是的，我知道一些编译器会将除以8的操作转换为一次移位，但这取决于编译器。)
它已经测试了高达2^32-2位（大约存储在536兆字节中的40亿位），尽管最后2位应该是可以访问的，如果没有在您的应用程序的for循环中使用。
请参见下面来自文档的摘录：http://alfredo4570.net/src/alflb_doco/alflb.pdf，库是http://alfredo4570.net/src/alflb.zip
祝您使用愉快，
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.
//------------------------------------------------------------------
- alf
1
一些编译器将除以8的操作转换为移位操作 - 在本世纪编写的编译器中是否存在不这样做的？ :) - Björn Lindqvist
3
你可以使用 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;
}
}
- Brian R. Bondy
2
你编译过这个吗？bitset支持按位与和按位或吗？ - Nathan Fellman
1你编译过这个吗？没有。bitset支持按位与和或运算吗？是的，有operator&和operator|重载，如此文档所述：http://www.sgi.com/tech/stl/bitset.html。 - Brian R. Bondy
2
我知道这是一篇旧帖子，但我来到这里寻找一个简单的C位集实现，而且没有任何答案完全符合我的要求，所以我根据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;
}
- Samwhoo
1
我使用这个：
。
//#include <bitset>
#include <iostream>
//source https://dev59.com/z3VD5IYBdhLWcg3wOo5h
#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))
- Roel911
2
为什么我们应该使用它？在这里给出一些解释！ - rayryeng
1在大多数实现中，布尔值的成本为1字节，在这种方法中，所需的内存空间可以缩小高达8倍，但代价是一些速度。 - Roel911
1
我最近实现了一个小型的头文件库，叫做BitContainer，专门用于这个目的。它侧重于表达能力和编译时能力，可以在此处找到: https://github.com/EddyXorb/BitContainer
它肯定不是查看位数组的传统方式，但对于强类型目的和命名属性的内存有效表示非常有用。
示例:
示例:
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
- EddyXorb
1
在微控制器开发中，有时我们需要使用元素值仅为 [0, 1] 的二维数组（矩阵）。这意味着如果我们使用 1 字节作为元素类型，它会极大地浪费内存（微控制器的内存非常有限）。建议的解决方案是使用 1 位矩阵（元素类型为 1 位）。
http://htvdanh.blogspot.com/2016/09/one-bit-matrix-for-cc-programming.html
- Danh Hoang
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
std::vector<bool>不可用，因此我在下面发布了一个传统的C位集实现。 - Dale Hagglund