सी/सी ++ कुशल बिट सरणी

Question

क्या आप मनमाना लंबाई बिट सरणी में हेरफेर करने के लिए कुशल/साफ तरीका सुझा सकते हैं?

अभी मैं नियमित int/char bitmask का उपयोग कर रहा हूं, लेकिन जब सरणी की लंबाई डेटाटाइप लंबाई से अधिक होती है तो वे बहुत साफ नहीं होते हैं।

std vector<bool> मेरे लिए उपलब्ध नहीं है।

Answer 1

boost::dynamic_bitset यदि लंबाई केवल रन समय में ही जानी जाती है।

std::bitset यदि लंबाई संकलित समय में ज्ञात है (हालांकि मनमाने ढंग से)।

Answer 2

आप उपयोग कर सकते हैं 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

जब से तुम सी के साथ ही सी ++ का उल्लेख है, मैं मान लेंगे कि एक सी ++ - उन्मुख boost::dynamic_bitset तरह समाधान लागू नहीं हो सकता है, और एक निम्न स्तर के सी कार्यान्वयन के बारे में बात बजाय। ध्यान दें कि अगर boost::dynamic_bitset आपके लिए कुछ काम करता है, या कोई पूर्व-मौजूदा सी लाइब्रेरी है जो आप पा सकते हैं, तो उनका उपयोग करके स्वयं को रोल करने से बेहतर हो सकता है।

चेतावनी: निम्न में से कोई भी कोड परीक्षण या संकलित नहीं किया गया है, लेकिन यह आपको आवश्यकतानुसार बहुत करीब होना चाहिए।

शुरू करने के लिए, मान लें कि आप एक निश्चित bitset आकार एन फिर निम्न कार्य की तरह कुछ है:

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 लागू करता है । इन समस्याओं का समाधान करने के लिए, आप निम्नलिखित की तरह एक डेटा struture कुछ के साथ शुरू करना चाहते हैं:

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

और फिर बना सकते हैं और इन 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); 
} 

अब, यह अपेक्षाकृत एक struct bitset * पैरामीटर लेने के लिए पिछले कार्यों को संशोधित करने के सीधा है। अपने जीवनकाल के दौरान एक बिटसेट को फिर से आकार देने का कोई तरीका नहीं है, न ही कोई सीमा जांच रही है, लेकिन इस बिंदु पर न तो जोड़ना मुश्किल होगा।

Answer 4

मैंने सी (बीएसडी लाइसेंस) में थोड़ा सरणी प्रदान करने के लिए Dale Hagglund's response के आधार पर एक कार्यशील कार्यान्वयन लिखा है।

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

कृपया मुझे पता आप क्या सोचते हैं/सुझाव दे। मुझे उम्मीद है कि इस सवाल का जवाब तलाशने वाले लोगों को यह उपयोगी लगेगा।

Answer 5

यह पोस्टिंग पुरानी है, लेकिन मेरी ALFLB लाइब्रेरी में सी में एक कुशल बिट सरणी सूट है।

हार्डवेयर-डिवीजन ओपोड के बिना कई माइक्रोकंट्रोलर के लिए, यह लाइब्रेरी प्रभावी है क्योंकि यह विभाजन का उपयोग नहीं करती है: इसके बजाय, मास्किंग और बिट-स्थानांतरण का उपयोग किया जाता है। (हाँ, मुझे पता है कि कुछ कंपाइलर्स 8 से एक शिफ्ट में विभाजन को परिवर्तित करेंगे, लेकिन यह कंपाइलर से कंपाइलर में भिन्न होता है।)

यह 2^32-2 बिट्स तक के सरणी पर परीक्षण किया गया है (लगभग 4 बिलियन बिट्स में संग्रहीत 536 एमबीइट्स), हालांकि पिछले 2 बिट्स को आपके एप्लिकेशन में फॉर-लूप में उपयोग नहीं किया जाना चाहिए।

डॉको से निकालने के लिए नीचे देखें। Doco 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. 
//------------------------------------------------------------------ 

Answer 6

है मैं जानता हूँ कि यह एक पुरानी पोस्ट है, लेकिन मैं यहाँ काफी मिलान किया कि मैं क्या था आया एक साधारण सी bitset कार्यान्वयन और जवाब में से कोई भी खोजने के लिए की तलाश में, इसलिए मैंने अपना खुद का डेल हैग्लुंड के उत्तर पर आधारित किया। यहाँ है :)

#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

मैं का उपयोग इस एक:

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

मैं हाल ही में BITSCAN, जो विशेष रूप तेजी से बिट स्कैनिंग आपरेशन की ओर उन्मुख है एक सी ++ बिट श्रृंखला के पुस्तकालय जारी किया है। बिटकैन here उपलब्ध है। यह अल्फा में है लेकिन अभी भी बहुत अच्छी तरह से परीक्षण किया गया है क्योंकि मैंने हाल के वर्षों में संयोजन अनुकूलन में अनुसंधान के लिए इसका उपयोग किया है (उदाहरण के लिए BBMC, कला सटीक अधिकतम क्लिक्स एल्गोरिदम की स्थिति)। अन्य प्रसिद्ध सी ++ कार्यान्वयन (एसटीएल या बूस्ट) के साथ तुलना here मिल सकती है।

मुझे आशा है कि आपको यह उपयोगी लगेगा। कोई प्रतिक्रिया स्वागत है।

Answer 9

माइक्रो नियंत्रक विकास में, कुछ बार हमें 2-आयामी सरणी (मैट्रिक्स) का उपयोग केवल [0, 1] के तत्व मान के साथ करने की आवश्यकता है। का अर्थ है कि यदि हम तत्व प्रकार के लिए 1 बाइट का उपयोग करते हैं, तो यह मेमोरी को बहुत खराब करता है (माइक्रो नियंत्रक की स्मृति बहुत सीमित है)। प्रस्तावित समाधान है कि हमें 1 बिट मैट्रिक्स का उपयोग करना चाहिए (तत्व प्रकार 1 बिट है)।

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