c - सी में बिट्स की सरणी के साथ कैसे परिभाषित और काम करना है?




arrays multidimensional-array (4)

अगर मुझे बहुत देर नहीं हुई है, तो this पृष्ठ उदाहरणों के साथ शानदार स्पष्टीकरण देता है।

bits सरणी से निपटने के लिए int की एक सरणी का उपयोग किया जा सकता है। int आकार को 4 bytes मानते हैं, जब हम किसी int बारे में बात करते हैं, तो हम 32 bits निपट रहे हैं। मान लें कि हमारे पास int A[10] , इसका मतलब है कि हम 10*4*8 = 320 bits पर काम कर रहे हैं और निम्न चित्र यह दिखाता है: (सरणी के प्रत्येक तत्व में 4 बड़े ब्लॉक होते हैं, जिनमें से प्रत्येक byte और प्रत्येक छोटे ब्लॉक का प्रतिनिधित्व करता है bit प्रतिनिधित्व)

तो, सरणी में के वें बिट सेट करने के लिए A :

void  SetBit( int A[],  int k )
   {
      int i = k/32;        //gives the corresponding index in the array A
      int pos = k%32;      //gives the corresponding bit position in A[i]

      unsigned int flag = 1;   // flag = 0000.....00001

      flag = flag << pos;      // flag = 0000...010...000   (shifted k positions)

      A[i] = A[i] | flag;      // Set the bit at the k-th position in A[i]
   }

या संक्षिप्त संस्करण में

void  SetBit( int A[],  int k )
   {
      A[k/32] |= 1 << (k%32);  // Set the bit at the k-th position in A[i]
   }

इसी तरह के स्पष्ट करने के लिए:

void  ClearBit( int A[],  int k )                
   {
      A[k/32] &= ~(1 << (k%32));
   }

और परीक्षण करने के लिए अगर के वें बिट:

int TestBit( int A[],  int k )
   {
      return ( (A[k/32] & (1 << (k%32) )) != 0 ) ;     
   }

जैसा ऊपर बताया गया है, इन जोड़ों को मैक्रोज़ के रूप में भी लिखा जा सकता है:

#define SetBit(A,k)     ( A[(k/32)] |= (1 << (k%32)) )
#define ClearBit(A,k)   ( A[(k/32)] &= ~(1 << (k%32)) )            
#define TestBit(A,k)    ( A[(k/32)] & (1 << (k%32)) )

मैं एक बहुत बड़ी सरणी बनाना चाहता हूं जिस पर मैं '0 और' 1 लिखता हूं। मैं यादृच्छिक अनुक्रमिक सोखना नामक एक भौतिक प्रक्रिया को अनुकरण करने की कोशिश कर रहा हूं, जहां लंबाई 2, dimers की इकाइयां एक यादृच्छिक स्थान पर एक-आयामी जाली पर जमा की जाती हैं, बिना किसी दूसरे को ओवरलैप किए। जब प्रक्रिया अधिक मंदियों को जमा करने के लिए जाली पर कोई और कमरा नहीं छोड़ा जाता है तो प्रक्रिया बंद हो जाती है (जाली जाम है)।

शुरुआत में मैं शून्यों की जाली से शुरू करता हूं, और dimers को '1' की एक जोड़ी द्वारा दर्शाया जाता है। चूंकि प्रत्येक डिमर जमा किया जाता है, इसलिए धुंध के बाईं ओर स्थित साइट अवरुद्ध होती है, इस तथ्य के कारण कि dimers ओवरलैप नहीं हो सकता है। तो मैं जाली पर '1 के तीन गुना जमा करके इस प्रक्रिया का अनुकरण करता हूं। मुझे पूरे सिमुलेशन को बड़ी संख्या में दोहराना होगा और फिर औसत कवरेज% का काम करना होगा।

मैंने पहले ही 1 डी और 2 डी लैटिस के लिए वर्णों की सरणी का उपयोग करके यह किया है। फिलहाल मैं 3 डी समस्या और अधिक जटिल सामान्यीकरण पर काम करने से पहले कोड को यथासंभव कुशल बनाने की कोशिश कर रहा हूं।

यह मूल रूप से 1 डी में कोड जैसा दिखता है, सरलीकृत:

int main()
{
    /* Define lattice */
    array = (char*)malloc(N * sizeof(char));

    total_c = 0;

    /* Carry out RSA multiple times */
    for (i = 0; i < 1000; i++)
        rand_seq_ads();

    /* Calculate average coverage efficiency at jamming */
    printf("coverage efficiency = %lf", total_c/1000);

    return 0;
}

void rand_seq_ads()
{
    /* Initialise array, initial conditions */
    memset(a, 0, N * sizeof(char));
    available_sites = N;
    count = 0;

    /* While the lattice still has enough room... */
    while(available_sites != 0)
    {
        /* Generate random site location */
        x = rand();

        /* Deposit dimer (if site is available) */
        if(array[x] == 0)
        {
            array[x] = 1;
            array[x+1] = 1;
            count += 1;
            available_sites += -2;
        }

        /* Mark site left of dimer as unavailable (if its empty) */
        if(array[x-1] == 0)
        {
            array[x-1] = 1;
            available_sites += -1;
        }
    }

    /* Calculate coverage %, and add to total */
    c = count/N
    total_c += c;
}

वास्तविक परियोजना के लिए मैं कर रहा हूं, इसमें केवल मंदर नहीं हैं लेकिन ट्रिमर्स, क्वाड्रिमर, और आकार और आकार के सभी प्रकार (2 डी और 3 डी के लिए) शामिल हैं।

मैं उम्मीद कर रहा था कि मैं बाइट्स के बजाय अलग-अलग बिट्स के साथ काम करने में सक्षम हूं, लेकिन मैं चारों ओर पढ़ रहा हूं और जहां तक ​​मैं कह सकता हूं कि आप एक समय में केवल 1 बाइट बदल सकते हैं, इसलिए मुझे कुछ जटिल अनुक्रमण करना होगा या ऐसा करने का एक आसान तरीका है?

आपके उत्तरों के लिए धन्यवाद


आप और (bitwise और) और << (बाएं शिफ्ट) का उपयोग कर सकते हैं।

उदाहरण के लिए, (1 << 3) परिणाम बाइनरी में "00001000" में परिणाम। तो आपका कोड इस तरह दिख सकता है:

char eightBits = 0;

//Set the 5th and 6th bits from the right to 1
eightBits &= (1 << 4);
eightBits &= (1 << 5);
//eightBits now looks like "00110000". 

फिर इसे वर्णों की एक सरणी के साथ स्केल करें और पहले संशोधित करने के लिए उपयुक्त बाइट को समझें।

अधिक दक्षता के लिए, आप पहले से बिटफील्ड की एक सूची परिभाषित कर सकते हैं और उन्हें एक सरणी में डाल सकते हैं:

#define BIT8 0x01
#define BIT7 0x02
#define BIT6 0x04
#define BIT5 0x08
#define BIT4 0x10
#define BIT3 0x20
#define BIT2 0x40
#define BIT1 0x80

char bits[8] = {BIT1, BIT2, BIT3, BIT4, BIT5, BIT6, BIT7, BIT8};

फिर आप बिट स्थानांतरण के ऊपरी हिस्से से बचें और आप अपने बिट्स को इंडेक्स कर सकते हैं, पिछले कोड को चालू कर सकते हैं:

eightBits &= (bits[3] & bits[4]);

वैकल्पिक रूप से, यदि आप सी ++ का उपयोग कर सकते हैं, तो आप केवल एक std::vector<bool> उपयोग कर सकते हैं जिसे आंतरिक रूप से बिट्स के वेक्टर के रूप में परिभाषित किया जाता है, जो प्रत्यक्ष अनुक्रमण के साथ पूर्ण होता है।


bitarray.h :

#include <inttypes.h> // defines uint32_t

//typedef unsigned int bitarray_t; // if you know that int is 32 bits
typedef uint32_t bitarray_t;

#define RESERVE_BITS(n) (((n)+0x1f)>>5)
#define DW_INDEX(x) ((x)>>5)
#define BIT_INDEX(x) ((x)&0x1f)
#define getbit(array,index) (((array)[DW_INDEX(index)]>>BIT_INDEX(index))&1)
#define putbit(array, index, bit) \
    ((bit)&1 ?  ((array)[DW_INDEX(index)] |= 1<<BIT_INDEX(index)) \
             :  ((array)[DW_INDEX(index)] &= ~(1<<BIT_INDEX(index))) \
             , 0 \
    )

उपयोग:

bitarray_t arr[RESERVE_BITS(130)] = {0, 0x12345678,0xabcdef0,0xffff0000,0};
int i = getbit(arr,5);
putbit(arr,6,1);
int x=2;            // the least significant bit is 0
putbit(arr,6,x);    // sets bit 6 to 0 because 2&1 is 0
putbit(arr,6,!!x);  // sets bit 6 to 1 because !!2 is 1

दस्तावेज़ संपादित करें :

"dword" = "डबल शब्द" = 32-बिट मान (हस्ताक्षरित, लेकिन यह वास्तव में महत्वपूर्ण नहीं है)

RESERVE_BITS: number_of_bits --> number_of_dwords
    RESERVE_BITS(n) is the number of 32-bit integers enough to store n bits
DW_INDEX: bit_index_in_array --> dword_index_in_array
    DW_INDEX(i) is the index of dword where the i-th bit is stored.
    Both bit and dword indexes start from 0.
BIT_INDEX: bit_index_in_array --> bit_index_in_dword
    If i is the number of some bit in the array, BIT_INDEX(i) is the number
    of that bit in the dword where the bit is stored.
    And the dword is known via DW_INDEX().
getbit: bit_array, bit_index_in_array --> bit_value
putbit: bit_array, bit_index_in_array, bit_value --> 0

getbit(array,i) थोड़ा सा युक्त शब्द getbit(array,i) और मुझे सही getbit(array,i) बदलता है, ताकि थोड़ा सा मैं कम से कम महत्वपूर्ण हो getbit(array,i) । फिर, थोड़ा सा और 1 के साथ सभी अन्य बिट्स साफ़ करता है।

putbit(array, i, v) सबसे पहले putbit(array, i, v) के कम से कम महत्वपूर्ण बिट की जांच करता है; यदि यह 0 है, तो हमें थोड़ा साफ़ करना होगा, और यदि यह 1 है, तो हमें इसे सेट करना होगा।
बिट सेट करने के लिए, हम थोड़ा सा या डवर्ड करते हैं जिसमें बिट होता है और 1 का मान bit_index_in_dword द्वारा छोड़ा गया है: वह बिट सेट है, और अन्य बिट्स नहीं बदलते हैं।
बिट को साफ़ करने के लिए, हम थोड़ा सा और उस कीवर्ड के बारे में बताते हैं जिसमें bit_ bitex_in_dword द्वारा छोड़ा गया 1 बिट और बिटवाईव पूरक है: उस मान में सभी बिट्स को उस स्थिति में केवल शून्य बिट को छोड़कर एक को सेट किया गया है जिसे हम साफ़ करना चाहते हैं।
मैक्रो के साथ समाप्त होता है , 0 क्योंकि अन्यथा यह उस शब्द के मूल्य को वापस कर देगा जहां बिट को संग्रहीत किया जाता है, और वह मान सार्थक नहीं है। कोई भी ((void)0) उपयोग कर सकता है ((void)0)


typedef unsigned long bfield_t[ size_needed/sizeof(long) ];
// long because that's probably what your cpu is best at
// The size_needed should be evenly divisable by sizeof(long) or
// you could (sizeof(long)-1+size_needed)/sizeof(long) to force it to round up

अब, प्रत्येक bfield_t में लंबे समय तक आकार (लंबी) * 8 बिट्स हो सकता है।

आप एक आवश्यक बड़े सूचकांक की गणना कर सकते हैं:

bindex = index / (8 * sizeof(long) );

और आपके बिट नंबर द्वारा

b = index % (8 * sizeof(long) );

फिर आप जितनी देर चाहें उतनी देर देख सकते हैं और फिर उस चीज़ को मुखौटा कर सकते हैं जिसकी आपको आवश्यकता है।

result = my_field[bindex] & (1<<b);

या

result = 1 & (my_field[bindex]>>b); // if you prefer them to be in bit0

पहला सीपीयू पर तेज़ हो सकता है या आप को वापस ले जाने से बचा सकता है, आपको कई बिट एरे में एक ही बिट के बीच संचालन करने की आवश्यकता है। यह दूसरे कार्यान्वयन की तुलना में क्षेत्र में थोड़ा सा सेटिंग और समाशोधन को भी प्रतिबिंबित करता है। सेट:

my_field[bindex] |= 1<<b;

स्पष्ट:

my_field[bindex] &= ~(1<<b);

आपको याद रखना चाहिए कि आप खेतों को पकड़ने वाले लंबे समय तक बिटवाईर ऑपरेशंस का उपयोग कर सकते हैं और यह अलग-अलग बिट्स पर संचालन के समान है।

यदि आप उपलब्ध हों तो आप शायद एफएफएस, एफएलएस, एफएफसी, और फ्लैक फ़ंक्शन में भी देखना चाहेंगे। ffs हमेशा strings.h में उपलब्ध होना चाहिए। यह सिर्फ इस उद्देश्य के लिए है - बिट्स की एक स्ट्रिंग। वैसे भी, यह पहला सेट और अनिवार्य रूप से मिलता है:

int ffs(int x) {
    int c = 0;
    while (!(x&1) ) {
        c++;
        x>>=1;
    }
    return c; // except that it handles x = 0 differently
}

प्रोसेसर के लिए निर्देश होने के लिए यह एक आम ऑपरेशन है और आपका कंपाइलर संभवतः उस निर्देश को उत्पन्न करने के बजाए उस निर्देश को उत्पन्न करेगा जैसा मैंने लिखा था। x86 इस तरह से एक निर्देश है। ओह, और ffsl और ffsll क्रमशः लंबे और लंबे समय तक छोड़कर एक ही कार्य हैं।







bitarray