إنشاء أرقام متعددة مع عدد معين من البتات مجموعة

Question

مشكلة

ولست بحاجة لخلق 32 الأرقام بت (وقعت أو غير موقعة لا يهم، لن يتم تعيين أعلى قليلا على أي حال) ويجب أن يكون كل رقم لعدد معين من القطع الموضوعة.

الحل ساذج

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

وأفضل الحلول

وأبسط عدد جود (دعنا نقول) 5 بت وضع هو رقم حيث يتم تعيين أول بت 5. يمكن خلق هذا الرقم بسهولة. ضمن حلقة تم تعيين بت الأول وتحول العدد إلى اليسار من جانب واحد. تدير هذه الحلقة 5 مرات ووجدت الرقم الأول مع 5 القطع الموضوعة. القليلة القادمة من الأرقام من السهل لخلق كذلك. نحن نتظاهر الآن أن يكون عدد 6 بت واسعة ولم يتم تعيين أعلى واحد. الآن نبدأ تحويل بت صفر الأول إلى اليمين، حتى نحصل على 101111، 110111، 111011، 111101، 111110. ويمكن تكرار ذلك عن طريق إضافة آخر 0 إلى الأمام وتكرار هذه العملية. 0111110، 1011110، 1101110، وما إلى ذلك بهذه الطريقة سوف أرقام تنمو أسرع بكثير مما هو ضروري، وباستخدام هذا النهج بسيط نترك من الأرقام 1010111.

وحتى لا يكون هناك طريقة أفضل لتهيئة جميع التبديلات الممكنة، وهو النهج العام، والتي يمكن استخدامها، بغض النظر عن كيفية العديد بت الرقم التالي سيكون وبغض النظر عن كيفية العديد بت مجموعة نحن بحاجة إلى وضع؟

Answer 1

ويمكنك استخدام بت twiddling الإختراق من hackersdelight.org .

في كتابه لديه رمز للحصول على عدد أكبر المقبل مع نفس العدد من مجموعة بت واحد.

إذا كنت تستخدم هذا بمثابة بدائية لزيادة عدد الخاص بك كل ما عليك القيام به هو العثور على نقطة البداية. الحصول على الرقم الأول مع بت N تحديد أمرا سهلا. انها مجرد 2 ^ (N-1) -1.

وسوف تكرار خلال جميع الأرقام الممكنة سريع جدا بهذه الطريقة.

  unsigned next_set_of_n_elements(unsigned x) 
  {
     unsigned smallest, ripple, new_smallest, ones;

     if (x == 0) return 0;
     smallest     = (x & -x);
     ripple       = x + smallest;
     new_smallest = (ripple & -ripple);
     ones         = ((new_smallest/smallest) >> 1) - 1;
     return ripple | ones;
  }

  // test code (shown for two-bit digits)

  void test (void)
  {
    int bits = 2;
    int a = pow(2,bits) - 1;
    int i;

    for (i=0; i<100; i++)
    {
       printf ("next number is %d\n", a);
       a = next_set_of_n_elements(a);
    }
  }

Answer 2

وحاول الاقتراب من المشكلة من الطريق المعاكس الجولة - ما نحاول القيام به هو ما يعادل "العثور على <م> ن أرقام في حدود 0-31"

لنفترض انك كنت في محاولة للعثور 4 أرقام. عليك أن تبدأ مع [0،1،2،3] ومن ثم زيادة عدد اخر في كل مرة (الحصول على [0،1،2،4]، [0،1،2،5] ...) حتى تصل إلى الحد [0،1،2،31]. ثم زيادة عدد ما قبل الأخير، وتعيين آخر رقم واحد أعلى: [0،1،3،4]. العودة الى زيادة عدد اخر: [0،1،3،5]، [0،1،3،6] ... وما إلى ذلك بمجرد أن تصل إلى نهاية هذا، كنت أعود إلى [0،1،4 5] - في نهاية المطاف أن تصل إلى [0،1،30،31] وعند هذه النقطة لديك للتراجع خطوة واحدة أبعد من ذلك: [0،2،3،4] وقبالة تذهب مرة أخرى. الاستمرار حتى النهاية في نهاية المطاف مع [28،29،30،31].

وبالنظر إلى مجموعة من الأرقام، فإنه من السهل الواضح لتحويلها إلى أرقام 32 بت.

Answer 3

وأنت تريد توليد مجموعات، انظر هذا ويكيبيديا المقالة .

Answer 4

وتحتاج إما التباديل Factoradic (جوجل على ذلك) أو أحد خوارزميات على المعرفة