طريقة سريعة لمعرفة حساب التكافؤ من بيتفيكتور

Question

أنا أعمل مع بيتفكتورس في ج.بلدي بيتفكتورس هي unsigned long longالصورة.بالنسبة لعدد كبير من المتجهات ، أحتاج إلى معرفة ما إذا كان التكافؤ ، أي.عدد البتات التي هي 1 ، زوجي أو فردي.

القيمة الدقيقة ليست مهمة ، فقط التكافؤ.كنت أتساءل عما إذا كان هناك أي شيء أسرع من حساب عدد الآحاد والتحقق.حاولت التفكير في شيء ما ، لكنني لم أجد أي شيء.

مثال قصير على كيف أريد أن يعمل هذا:

void checkIntersection(unsigned long long int setA, unsigned long long int setB){
    if(isEven(setA & setB)){
        //do something
    }
}

Answer 1

مع تقنية فرق تسد:

uint64_t a = value;
a ^= (a >> 32);            // Fold the 32 MSB over the 32 LSB
a ^= (a >> 16);            // reducing the problem by 50%
a ^= (a >> 8);             // <-- this can be a good break even point
..
return lookup_table[a & 0xff];  // 16 or 256 entries are typically good
..

يمكن تطبيق إجراء الطي حتى النهاية:

a ^= (a >> 1);
return a & 1;

في يا العلم التكافؤ يمكن استرجاعها مباشرة بعد التخفيض إلى 8 بت.

a ^= (a >> 4); يجعل نقطة جيدة أخرى لوقف الانقسام ، لأن بعض أبنية المعالج يمكن أن توفر جداول بحث متوازية uint8_t LUT[16] جزءا لا يتجزأ من شكسم (أو النيون) السجلات.أو ببساطة ذاكرة التخزين المؤقت المحتملة يخطئ من 256 دخول لوت يمكن ببساطة زيادة الوزن المهمة الحسابية من جولة إضافية واحدة.من الأفضل بطبيعة الحال قياس حجم طرفية هو الأمثل في بنية معينة.

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

return ((TRUTH_TABLE_FOR_PARITY) >> (a & 15)) & 1;

أين بت N من الثابت السحري أعلاه يشفر القيمة المنطقية لـ التكافؤ (ن).

Answer 2

يمكنك الإعجاب في صفيف التكافؤ لجميع المجموعات الممكنة من البتات في البايت:

giveacodicetagpre.

عندما تحتاج إلى معرفة التكافؤ من صفيف أكبر، يمكنك فقط القيام به:

giveacodicetagpre.

إخلاء المسئولية: لم أختبر التعليمات البرمجية، إنها مجرد فكرة.

Answer 3

سهل جدا.شيء مثل

giveacodicetagpre. يجب أن تعمل

.أيضا، بعض وحدات المعالجة المركزية لديها تعليمات عدد السكان (لا أعتقد أن x86، العقل).

إذا كنت تحب هذا النوع من الأشياء، يجب عليك التحقق من الكتاب Hacker's Delight من Henry S. Warren، JR.