صفيف C/C ++ بت أو متجه بت

Question

أنا أتعلم برمجة C/C ++ وواجهت استخدام "صفائف بت" أو "ناقلات بت". أنا غير قادر على فهم هدفهم؟ ها هي شكوكي -

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.

الآن ، نحن قادرون على اختبار ما إذا كان مثل هذا الخطأ قد حدث من خلال تطبيق مكعب bitmas. على سبيل المثال ، إذا كنت تريد العمل إذا كان خطأ 8 لقد حدث ، استخدم تمثيل بت 8 = 00001000. الآن ، من أجل استخراج ما إذا كان هذا الخطأ قد حدث أم لا ، استخدم ثنائيًا ومثل ذلك:

  00001101
& 00001000
= 00001000

أنا متأكد من أنك تعرف كيف تعمل AN أو يمكنك استنتاجها من ما سبق - أرقام العمل ، إذا كان هناك رقمين كلاهما 1 ، فإن النتيجة هي 1 ، وإلا فهي 0.

الآن ، في ج:

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

الآن ، إلى الجوانب العملية. عندما كانت الذاكرة متناثرة ولم يكن للبروتوكولات رفاهية XML المطوّلة ، كان من الشائع تحديد الحقل بقدر العديد من البتات. في هذا الحقل ، تقوم بتعيين أجزاء مختلفة (أعلام ، قوى 2) لمعنى معين وتطبيق العمليات الثنائية على الاستنتاج إذا تم تعيينها ، ثم تعمل على هذه.

يجب أن أضيف أيضًا أن العمليات الثنائية قريبة من الفكرة إلى الإلكترونيات الأساسية لجهاز الكمبيوتر. تخيل لو أن حقول البت تتوافق مع إخراج الدوائر المختلفة (تحمل التيار أم لا). باستخدام مجموعات كافية من الدوائر المذكورة ، تصنع ... جهاز كمبيوتر.

Answer 2

فيما يتعلق بالاستخدام صفيف البتات:

إذا كنت تعرف أن هناك 1 مليون رقم "فقط" - فأنت تستخدم مجموعة من مليون بت. في البداية ، ستكون جميع البتات صفرًا وفي كل مرة تقرأ فيها رقمًا - استخدم هذا الرقم كفهرس وتغيير البت في هذا الفهرس ليكون واحدًا (إذا لم يكن واحدًا بالفعل).

بعد قراءة جميع الأرقام - الأرقام المفقودة هي مؤشرات الأصفار في الصفيف.

على سبيل المثال ، إذا كان لدينا أرقام فقط بين 0 - 4 ، ستبدو الصفيف هكذا في البداية: 0 0 0 0 0. إذا قرأنا الأرقام: 3 ، 2 ، 2 ، ستبدو المصفوفة مثل: قراءة 3 - > 0 0 0 1 0. اقرأ 3 (مرة أخرى) -> 0 0 0 1 0. اقرأ 2 -> 0 0 1 1 0. تحقق من مؤشرات الأصفار: 0،1،4 -هذه هي الأرقام المفقودة

راجع للشغل ، بالطبع يمكنك استخدام الأعداد الصحيحة بدلاً من البتات ولكن قد يستغرق الأمر (يعتمد على النظام) ذاكرة 32 مرة

سيفان

Answer 3

يمكن أن تكون صفائف البت أو ناقلات البتات على الرغم من مجموعة من القيم المنطقية. عادةً ما يحتاج المتغير المنطقي إلى تخزين بايت واحد على الأقل ، ولكن في صفيف/متجه صغير ، هناك حاجة إلى بت واحد فقط. يصبح هذا مفيدًا إذا كان لديك الكثير من هذه البيانات حتى تقوم بحفظ الذاكرة بشكل عام.

استخدام آخر إذا كان لديك الأرقام التي لا تتناسب تمامًا مع المتغيرات القياسية والتي هي 8،16،32 أو 64 بت في الحجم. يمكنك بهذه الطريقة تخزينها في ناقل صغير من 16 بت يتكون من 4 بت ، واحد 2 بت والآخر في الحجم 10 بت. عادةً ما يتعين عليك استخدام 3 متغيرات بأحجام 8،8 و 16 بت ، لذلك لديك فقط 50 ٪ من التخزين يضيع.

ولكن نادرًا ما يتم استخدام كل هذه الاستخدامات في إزاحة الأعمال ، والاستخدام في كثير من الأحيان عند تواصل السائقين من خلال بينفوك/interop وظائف والقيام برمجة منخفضة المستوى.

Answer 4

يتم استخدام صفائف بت من ناقلات البت كخطط رسم الخرائط من موضع إلى قيمة بت. نعم ، إنه في الأساس نفس الشيء مثل مجموعة من المنسق ، ولكن تنفيذ Bool النموذجي يبلغ طوله من أربعة إلى أربعة بايت ويستخدم مساحة كبيرة.

يمكننا تخزين نفس الكمية من البيانات بشكل أكثر كفاءة باستخدام صفائف من الكلمات وعمليات التقنيع الثنائية والتحولات لتخزينها واستردادها (أقل إجمالية من الذاكرة المستخدمة ، وأقل وصول إلى الذاكرة ، وملكة تجهيز أقل ، ومبادلة صفحة الذاكرة أقل). لا يزال الرمز للوصول إلى البتات الفردية واضحًا تمامًا.

هناك أيضًا بعض الدعم الميداني المبني في لغة C (تكتب أشياء مثل int i:1; أن نقول "تستهلك بت واحد فقط") ، ولكنه غير متوفر للمصفوفات ولديك تحكم أقل في النتيجة الإجمالية (تعتمد تفاصيل التنفيذ على مشكلات التحويل البرمجي والمحاذاة).

فيما يلي طريقة ممكنة للإجابة على سؤال "البحث المفقود". لقد قمت بإصلاح حجم int إلى 32 بت للحفاظ على الأمور بسيطة ، ولكن يمكن كتابتها باستخدام SizeOF (int) لجعلها محمولة. و (اعتمادًا على المترجم ومعالج الهدف) لا يمكن جعل الرمز أسرع إلا باستخدام >> 5 بدلاً من / 32 و & 31 بدلاً من % 32, ، ولكن هذا فقط لإعطاء الفكرة.

#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

يتم استخدام ذلك لتخزين Bit Flags ، وكذلك لتحليل حقول بروتوكولات ثنائية مختلفة ، حيث يتم تقسيم بايت واحد إلى عدد من حقول البتات. يتم استخدام هذا على نطاق واسع ، في بروتوكولات مثل TCP/IP ، وحتى تشفير ASN.1 ، وحزم OpenPGP ، وما إلى ذلك.