सी/सी ++ बिट ऐरे या बिट वेक्टर

Question

मैं सी/सी ++ प्रोग्रामिंग & सीख रहा हूं 'बिट एरे' या 'बिट वेक्टर' के उपयोग का सामना करना पड़ा है। मैं उनके उद्देश्य को समझने में सक्षम नहीं हूं? यहां मेरे संदेह हैं -

1. क्या वे बूलियन झंडे के रूप में उपयोग किए जाते हैं?
2. क्या कोई इसके बजाय int सरणी का उपयोग कर सकता है? (पाठ्यक्रम की अधिक यादें, लेकिन ..)
3. बिट-मास्किंग की यह अवधारणा क्या है?
4. यदि बिट-मास्किंग उचित ध्वज प्राप्त करने के लिए सरल बिट ऑपरेशंस है, तो उनके लिए एक प्रोग्राम कैसे करें? क्या इस ऑपरेशन को सिर में करना मुश्किल नहीं है यह देखने के लिए कि ध्वज क्या होगा, दशमलव संख्याओं के लिए अपील की गई है?

मैं एप्लिकेशन की तलाश में हूं, ताकि मैं बेहतर समझ सकूं। उदाहरण के लिए -

प्रश्न आपको एक फ़ाइल (1 से 1 मिलियन) में पूर्णांक युक्त फ़ाइल दी गई है। कुछ डुप्लिकेट हैं और इसलिए कुछ संख्याएं गायब हैं। नंबरों को खोने का सबसे तेज़ तरीका खोजें?

उपरोक्त प्रश्न के लिए, मैंने थोड़ा सरणी का उपयोग करने के लिए मुझे बताए गए समाधान पढ़े हैं। एक बिट में प्रत्येक पूर्णांक कैसे स्टोर करेगा?

Answer 1

मुझे लगता है कि आप अपने आप को सरणियों और संख्याओं के बीच उलझन में मिल गया है, विशेष रूप से क्या यह द्विआधारी संख्या में हेरफेर करने का मतलब है।

मैं उदाहरण के लिए इसके बारे में जाऊंगा। मान लें कि आपके पास कई त्रुटि संदेश हैं और आप उन्हें फ़ंक्शन से रिटर्न वैल्यू में वापस करना चाहते हैं। अब, आप अपनी त्रुटियों को 1,2,3,4 लेबल कर सकते हैं ... जो आपके दिमाग को समझ में आता है, लेकिन फिर आप केवल एक नंबर के साथ कैसे काम करते हैं, यह पता लगाना कि कौन सी त्रुटियां हुई हैं?

अब, त्रुटियों को लेबल करने का प्रयास करें 1,2,4,8,16 ... मूल रूप से दो की शक्तियां बढ़ाना। यह क्यों काम करता है? खैर, जब आप बेस 2 पर काम करते हैं तो आप 00000000 जैसे नंबर को जोड़ रहे हैं, जहां प्रत्येक अंक दाईं ओर से अपनी स्थिति से 2 गुणा की शक्ति से मेल खाता है। तो मान लें कि त्रुटियां 1, 4 और 8 होती हैं। खैर, तो इसे 00001101 के रूप में प्रदर्शित किया जा सकता है। विपरीत में, पहला अंक = 1 * 2^0, तीसरा अंक 1 * 2^2 और चौथा अंक 1 * 2^3। उन्हें सब कुछ जोड़ना आपको 13.

अब, हम परीक्षण करने में सक्षम हैं कि बिटमैस्क लागू करके ऐसी कोई त्रुटि हुई है या नहीं। उदाहरण के लिए, अगर आप काम करना चाहते हैं तो त्रुटि 8 हुई है, तो 8 = 00001000 के बिट प्रतिनिधित्व का उपयोग करें। - काम कर रहा अंकों के लिहाज से

00001101 
& 00001000 
= 00001000 

मुझे यकीन है कि आप जानते हैं कि कैसे एक और काम करता है या ऊपर से यह अनुमान लगा सकते हैं कर रहा हूँ: अब, आदेश निकालने के लिए किया जाए या नहीं है कि त्रुटि हुई है, एक द्विआधारी और इतने की तरह उपयोग करें , यदि कोई दो अंक दोनों 1 कर रहे हैं, परिणाम 1 है, वरना यह 0.

अब है, C:

int func(...) 
{ 
    int retval = 0; 

    if (sometestthatmeans an error) 
    { 
     retval += 1; 
    } 


    if (sometestthatmeans an error) 
    { 
     retval += 2; 
    } 
    return retval 
} 

int anotherfunc(...) 
{ 
    uint8_t x = func(...) 

    /* binary and with 8 and shift 3 plaes to the right 
    * so that the resultant expression is either 1 or 0 */ 
    if (((x & 0x08) >> 3) == 1) 
    { 
     /* that error occurred */ 
    } 
} 

अब, चलन है। जब स्मृति स्पैस थी और प्रोटोकॉल में वर्बोज़ एक्सएमएल इत्यादि की लक्जरी नहीं थी, तो इतने सारे बिट्स के रूप में एक क्षेत्र को सीमित करना आम था। उस क्षेत्र में, आप एक निश्चित अर्थ के लिए विभिन्न बिट्स (झंडे, 2 की शक्तियां) असाइन करते हैं और यदि वे सेट हैं तो कटौती करने के लिए बाइनरी ऑपरेशंस लागू करते हैं, फिर इन पर काम करें।

मुझे यह भी जोड़ना चाहिए कि बाइनरी ऑपरेशंस कंप्यूटर के अंतर्निहित इलेक्ट्रॉनिक्स के विचार में नज़दीक हैं। कल्पना करें कि क्या बिट फ़ील्ड विभिन्न सर्किट (वर्तमान या नहीं ले जाने) के आउटपुट से मेल खाते हैं। कहा सर्किट के पर्याप्त संयोजनों का उपयोग करके, आप ... एक कंप्यूटर बनाते हैं।

Answer 2

उपयोग बिट्स सरणी के बारे में:

यदि आप जानते हैं "केवल" 1 लाख संख्या देखते हैं - आप 1 लाख बिट्स की एक एरे का उपयोग करें। शुरुआत में सभी बिट्स शून्य होंगे और हर बार जब आप कोई संख्या पढ़ते हैं - इस नंबर का उपयोग इंडेक्स के रूप में करें और इस इंडेक्स में बिट को एक होने के लिए बदलें (यदि यह पहले से कोई नहीं है)।

सभी संख्याओं को पढ़ने के बाद - गायब संख्या सरणी में शून्य के सूचकांक हैं।

उदाहरण के लिए, यदि हमारे पास 0 - 4 के बीच केवल संख्याएं थीं तो शुरुआत में यह दिखाई देगा: 0 0 0 0 0. यदि हम संख्याओं को पढ़ते हैं: 3, 2, 2 सरणी दिखाई देगी यह: 3 -> 0 0 0 1 पढ़ें 0 पढ़ें (फिर से) -> 0 0 0 1 0. पढ़ें 2 -> 0 0 1 1 0. शून्य के सूचकांक की जांच करें: 0,1,4 - उन लापता संख्या

BTW कर रहे हैं, बेशक आप बिट्स के बजाय पूर्णांक (सिस्टम पर निर्भर करता है) 32 बार स्मृति

सिवान

Answer 3

के लिए प्रयोग किया जाता है यही कारण है कि उपयोग कर सकते हैं, लेकिन यह लग सकता है बिट फ्लैग स्टोरेज, साथ ही विभिन्न बाइनरी प्रोटोकॉल फ़ील्ड को पार्स करने के लिए, जहां 1 बाइट कई बिट-फ़ील्ड में बांटा गया है। इसका व्यापक रूप से उपयोग किया जाता है, टीसीपी/आईपी जैसे प्रोटोकॉल में, एएसएन .1 एन्कोडिंग तक, ओपनपीजीपी पैकेट, और इसी तरह।

Answer 4

बिट वेक्टर के बिट एरेज़ को स्थिति से मैपिंग के रूप में कुछ बिट मान के रूप में उपयोग किया जाता है। हां यह मूल रूप से बूल की सरणी के समान ही है, लेकिन सामान्य बूल कार्यान्वयन एक से चार बाइट लंबा है और यह बहुत अधिक जगह का उपयोग करता है।

हम शब्दों और बाइनरी मास्किंग ऑपरेशंस के सरणी और उन्हें स्टोर करने और उन्हें पुनर्प्राप्त करने के लिए शिफ्टों का उपयोग करके अधिक मात्रा में डेटा स्टोर कर सकते हैं (कम समग्र स्मृति का उपयोग किया जाता है, स्मृति तक कम पहुंच, कम कैश मिस, कम मेमोरी पेज स्वैप)। अलग-अलग बिट्स तक पहुंचने के लिए कोड अभी भी काफी सरल है।

सी भाषा में कुछ बिट फील्ड समर्थन भी बनाया गया है (आप int i:1; जैसी चीजें लिखते हैं "केवल एक बिट का उपभोग करें"), लेकिन यह सरणी के लिए उपलब्ध नहीं है और आपके पास समग्र परिणाम का कम नियंत्रण है (विवरण कार्यान्वयन कंपाइलर और संरेखण मुद्दों पर निर्भर करता है)।

नीचे "खोज अनुपलब्ध संख्या" प्रश्न का उत्तर देने का एक संभावित तरीका नीचे दिया गया है। मैंने चीजों को सरल रखने के लिए 32 बिट्स के लिए int आकार तय किया है, लेकिन इसे पोर्टेबल बनाने के लिए आकार (int) का उपयोग करके लिखा जा सकता है। और (कंपाइलर और लक्ष्य प्रोसेसर के आधार पर) के बजाय >> 5 और % 32 के बजाय & 31 का उपयोग करके कोड को केवल तेज़ी से बनाया जा सकता है, लेकिन यह केवल विचार देने के लिए है।

#include <stdio.h> 
#include <errno.h> 
#include <stdint.h> 

int main(){ 
    /* put all numbers from 1 to 1000000 in a file, except 765 and 777777 */ 
    { 
     printf("writing test file\n"); 
     int x = 0; 
     FILE * f = fopen("testfile.txt", "w"); 
     for (x=0; x < 1000000; ++x){ 
      if (x == 765 || x == 777760 || x == 777791){ 
       continue; 
      } 
      fprintf(f, "%d\n", x); 
     } 
     fprintf(f, "%d\n", 57768); /* this one is a duplicate */ 
     fclose(f); 
    } 

    uint32_t bitarray[1000000/32]; 

    /* read file containing integers in the range [1,1000000] */ 
    /* any non number is considered as separator */ 
    /* the goal is to find missing numbers */ 
    printf("Reading test file\n"); 
    { 
     unsigned int x = 0; 
     FILE * f = fopen("testfile.txt", "r"); 
     while (1 == fscanf(f, " %u",&x)){ 
      bitarray[x/32] |= 1 << (x % 32); 
     } 
     fclose(f); 
    } 
    /* find missing number in bitarray */ 
    { 
     int x = 0; 
     for (x=0; x < (1000000/32) ; ++x){ 
      int n = bitarray[x]; 
      if (n != (uint32_t)-1){ 
       printf("Missing number(s) between %d and %d [%x]\n", 
        x * 32, (x+1) * 32, bitarray[x]); 
       int b; 
       for (b = 0 ; b < 32 ; ++b){ 
        if (0 == (n & (1 << b))){ 
         printf("missing number is %d\n", x*32+b); 
        } 
       } 
      } 
     } 
    } 
} 

Answer 5

बिट एरे या बिट वेक्टर हालांकि बूलियन मान के सरणी के रूप में हो सकते हैं। आम तौर पर एक बुलियन चर को कम से कम एक बाइट स्टोरेज की आवश्यकता होती है, लेकिन थोड़ा सरणी/वेक्टर में केवल एक बिट की आवश्यकता होती है। यदि आपके पास बहुत सारे डेटा हैं तो यह आसान हो जाता है ताकि आप बड़ी मेमोरी को बचा सकें।

एक और उपयोग यह है कि यदि आपके पास संख्याएं हैं जो मानक चर में बिल्कुल फिट नहीं हैं जो आकार में 8,16,32 या 64 बिट हैं। आप इस तरह से 16 बिट के एक बिट वेक्टर में स्टोर कर सकते हैं जिसमें 4 बिट होते हैं, एक जो 2 बिट होता है और एक आकार में 10 बिट होता है। आम तौर पर आपको 8,8 और 16 बिट के आकार के साथ 3 चर का उपयोग करना होगा, इसलिए आपके पास केवल 50% भंडारण बर्बाद हो गया है।

लेकिन इन सभी का उपयोग करता है बहुत मुश्किल से ही व्यापार aplications में उपयोग किया जाता है, जब के माध्यम से PInvoke/इंटरॉप कार्यों ड्राइवरों इंटरफ़ेस और निम्न स्तर प्रोग्रामिंग कर अक्सर उपयोग करने के लिए आते हैं।