Mảng bit hiệu dụng C/C++

Question

Bạn có thể đề xuất cách hiệu quả/sạch để thao tác mảng bit dài tùy ý không?

Ngay bây giờ tôi đang sử dụng bitmap bình thường int/char, nhưng chúng không phải là rất sạch sẽ khi chiều dài mảng lớn hơn chiều dài datatype.

std vector<bool> không có sẵn cho tôi.

Answer 1

boost::dynamic_bitset nếu độ dài chỉ được biết trong thời gian chạy.

std::bitset nếu độ dài được biết trong thời gian biên dịch (mặc dù tùy ý).

Answer 2

Bạn có thể sử dụng 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; 
    } 
} 

Answer 3

Kể từ khi bạn đề cập đến C cũng như C++, tôi sẽ giả định rằng một C++ - định hướng giải pháp như boost::dynamic_bitset có thể không được áp dụng, và nói về việc thực hiện C ở mức độ thấp thay thế. Lưu ý rằng nếu một cái gì đó như boost::dynamic_bitset hoạt động cho bạn hoặc có một thư viện C đã tồn tại từ trước, bạn có thể tìm thấy chúng, sau đó sử dụng chúng có thể tốt hơn là cuộn của riêng bạn.

Cảnh báo: Không có mã nào sau đây đã được thử nghiệm hoặc thậm chí được biên soạn, nhưng nó phải rất gần với những gì bạn cần.

Để bắt đầu, giả sử bạn có một bitset kích thước N. cố định Sau đó, một cái gì đó giống như các công việc sau:

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

Theo văn bản, đây là một chút dầu thô kể từ khi nó thực hiện chỉ một bitset toàn cầu duy nhất với một kích thước cố định . Để giải quyết những vấn đề này, bạn muốn bắt đầu với một dữ liệu có cấu trúc như sau:

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

và sau đó viết các chức năng để tạo và hủy các bit này.

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

Bây giờ, việc sửa đổi các chức năng trước đó để tham số struct bitset * là khá đơn giản. Vẫn không có cách nào để tái kích thước một bitet trong suốt cuộc đời của nó, cũng không có kiểm tra giới hạn nào, nhưng cũng không khó để thêm vào thời điểm này.

Answer 4

Tôi đã viết triển khai hoạt động dựa trên Dale Hagglund's response để cung cấp mảng bit trong C (giấy phép BSD).

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

Vui lòng cho tôi biết suy nghĩ của bạn/đưa ra đề xuất. Tôi hy vọng mọi người tìm kiếm câu trả lời cho câu hỏi này sẽ hữu ích.

Answer 5

Bài đăng này khá cũ, nhưng có một bộ mảng bit hiệu quả trong C trong thư viện ALFLB của tôi.

Đối với nhiều vi điều khiển không có mã opcode phân chia phần cứng, thư viện này là EFFICIENT vì nó không sử dụng phép chia: thay vào đó, sử dụng tính năng che và dịch chuyển bit. (Có, tôi biết một số trình biên dịch sẽ chuyển đổi phân chia theo 8 thành ca, nhưng điều này thay đổi từ trình biên dịch sang trình biên dịch.)

Nó đã được thử nghiệm trên mảng lên đến 2^32-2 bit (khoảng 4 tỷ bit được lưu trữ trong 536 MBytes), mặc dù 2 bit cuối cùng có thể truy cập được nếu không được sử dụng trong vòng lặp for trong ứng dụng của bạn.

Xem bên dưới để biết trích xuất từ ​​tài liệu. Doco là http://alfredo4570.net/src/alflb_doco/alflb.pdf, thư viện là http://alfredo4570.net/src/alflb.zip

Thưởng thức,
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. 
//------------------------------------------------------------------ 

Answer 6

Tôi biết đó là một bài cũ nhưng tôi đến đây để tìm một việc thực hiện C bitset đơn giản và không ai trong số các câu trả lời khá phù hợp những gì tôi đã tìm kiếm, vì vậy tôi đã tự thực hiện dựa trên câu trả lời của Dale Hagglund. Dưới đây là :)

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

Answer 7

tôi sử dụng cái này:

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

Answer 8

Gần đây tôi đã phát hành BITSCAN, C++ chút chuỗi thư viện được định hướng đặc biệt đối với hoạt động quét chút nhanh. BITSCAN có sẵn here. Nó ở dạng alpha nhưng vẫn được kiểm tra khá tốt vì tôi đã sử dụng nó trong những năm gần đây để nghiên cứu tối ưu hóa tổ hợp (ví dụ: BBMC, thuật toán clique tối đa chính xác). So sánh với các triển khai C++ nổi tiếng khác (STL hoặc BOOST) có thể được tìm thấy here.

Tôi hy vọng bạn thấy nó hữu ích. Bất kỳ thông tin phản hồi được chào đón.

Answer 9

Trong phát triển bộ điều khiển vi mô, đôi khi chúng tôi cần sử dụng mảng 2 chiều (ma trận) với giá trị phần tử chỉ [0, 1]. Điều đó có nghĩa là nếu chúng ta sử dụng 1 byte cho loại phần tử, nó lãng phí bộ nhớ rất nhiều (bộ nhớ của bộ điều khiển vi mô rất hạn chế). Giải pháp được đề xuất là mà chúng ta nên sử dụng ma trận 1 bit (loại phần tử là 1 bit).

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