بت uninterlace من قيمة 16 بت

Question

لدي قيمة 16 بت مع بتاتها "المتداخلة".

أريد الحصول على مجموعة من 8 عناصر (القيم 0 إلى 3) التي تخزن البتات في هذا الترتيب:

• البند 0: بت 7 و 15
• البند 1: بت 6 و 14
• البند 2: البتات 5 و 13
• ...
• البند 7: بت 0 و 8

هذا هو الحل التاف:

function uninterlace(n) {
  return [((n>>7)&1)|((n>>14)&2), // bits 7 and 15
          ((n>>6)&1)|((n>>13)&2), // bits 6 and 14
          ((n>>5)&1)|((n>>12)&2), // bits 5 and 13
          ((n>>4)&1)|((n>>11)&2), // bits 4 and 12
          ((n>>3)&1)|((n>>10)&2), // bits 3 and 11
          ((n>>2)&1)|((n>> 9)&2), // bits 2 and 10
          ((n>>1)&1)|((n>> 8)&2), // bits 1 and 9
          ((n>>0)&1)|((n>> 7)&2)];// bits 0 and 8
}

هل يعرف أحد وسيلة أفضل (أسرع) للقيام بذلك؟

يحرر:

ملاحظات:

• بناء جدول مسبق ليس خيارا.
• لا يمكن استخدام تحسينات المجمع أو وحدة المعالجة المركزية الخاصة

Answer 1

حسنا، الآن مع 3 عمليات لكل عنصر (تم اختباره ويعمل).

هذا هو الاختلاف في إجابة البوذراطية. يستخدم أقنعة ومتغيرة الشرائح.

function uninterlace(n) {     
     return [((n & 0x8080) + 0x3FFF) >> 14,
             ((n & 0x4040) + 0x1FFF) >> 13,
             ((n & 0x2020) + 0x0FFF) >> 12,
             ((n & 0x1010) + 0x07FF) >> 11,
             ((n & 0x0808) + 0x03FF) >> 10,
             ((n & 0x0404) + 0x01FF) >> 9,
             ((n & 0x0202) + 0x00FF) >> 8,
             ((n & 0x0101) + 0x007F) >> 7];
}

Answer 2

أسرع من حلقة مكتوبة يدويا غير مثبتة؟ أنا أشك في ذلك.

يمكن أن يكون الرمز أقل تسديدة باستخدام for-Loop، ولكن هذا لن يجعل من تشغيل أي أسرع.

Answer 3

def uninterlace(n) {
    mask = 0x0101 // 0b0000_0001_0000_0001
    slide = 0x7f  // 0b0111_1111
    return [(((n >> 0) & mask) + slide) >> 7,
            (((n >> 1) & mask) + slide) >> 7,
            (((n >> 2) & mask) + slide) >> 7,
            (((n >> 3) & mask) + slide) >> 7,
            (((n >> 4) & mask) + slide) >> 7,
            (((n >> 5) & mask) + slide) >> 7,
            (((n >> 6) & mask) + slide) >> 7,
            (((n >> 7) & mask) + slide) >> 7]
}

هذه ليست سوى أربع عمليات لكل إدخال، بدلا من 5. الحيلة في إعادة استخدام القيمة تحولت. إضافة slide يتحرك البتات ذات الصلة المتاخمة لبعضها البعض، والتحول بنسبة 7 يضعها في وضع الترتيب المنخفض. استخدام + قد يكون ضعف.

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

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

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

تحرير لتصحيح slide لكل تعليق بيدرو. آسف لاتخاذ وقتك في مهارات التحويل البعدية الفقيرة. كان في الأصل 0xef, ، مما يضع 0 بت في المكان الخطأ.

Answer 4

ماذا عن طاولة صغيرة مسبقة من 128 مخلفات مرات 2؟

int[128] b1 = { 2, 3, 3, .. 3};
int[128] b0 = { 0, 1, 1, .. 1};

function uninterlace(n) {
  return [(n & 0x8000) ? b1 : b0)[n & 0x80],
          (n & 0x4000) ? b1 : b0)[n & 0x40],
          (n & 0x2000) ? b1 : b0)[n & 0x20],
          (n & 0x1000) ? b1 : b0)[n & 0x10],
          (n & 0x0800) ? b1 : b0)[n & 0x08],
          (n & 0x0400) ? b1 : b0)[n & 0x04],
          (n & 0x0200) ? b1 : b0)[n & 0x02],
          (n & 0x0100) ? b1 : b0)[n & 0x01]
         ];
}

يستخدم هذا البت اخفاء والجدول بحث بدلا من التحولات والإضافات وقد يكون أسرع.