أسرع طريقة لحساب مجموع البتات في صفيف البايت

Question

لدي صفيفتان بايتان بنفس الطول. أحتاج إلى إجراء عملية XOR بين كل بايت وبعد هذا حساب مجموع البتات.

علي سبيل المثال:

11110000^01010101 = 10100101 -> so 1+1+1+1 = 4

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

Answer 1

استخدم جدول البحث. لا يوجد سوى 256 قيمًا محتملة بعد Xoring ، لذلك لن يستغرق الأمر وقتًا طويلاً. على عكس حل IZB ، لن أقترح وضع جميع القيم يدويًا - احسب جدول البحث بمجرد عند بدء التشغيل باستخدام أحد إجابات الحلقات.

علي سبيل المثال:

public static class ByteArrayHelpers
{
    private static readonly int[] LookupTable =
        Enumerable.Range(0, 256).Select(CountBits).ToArray();

    private static int CountBits(int value)
    {
        int count = 0;
        for (int i=0; i < 8; i++)
        {
           count += (value >> i) & 1;
        }
        return count;
    }

    public static int CountBitsAfterXor(byte[] array)
    {
        int xor = 0;
        foreach (byte b in array)
        {
            xor ^= b;
        }
        return LookupTable[xor];
    }
}

(أنت يستطع اجعلها طريقة تمديد إذا كنت تريد حقًا ...)

لاحظ استخدام byte[] في ال CountBitsAfterXor الطريقة - أنت يستطع اجعلها IEnumerable<byte> لمزيد من العمومية ، ولكن التكرار على صفيف (يُعرف أنه صفيف في وقت الترجمة) سيكون أسرع. ربما أسرع مجهريًا فقط ، لكن مهلا ، طلبت أسرع طريق :)

بالتأكيد أود فعلا عبر عنها

public static int CountBitsAfterXor(IEnumerable<byte> data)

في الحياة الحقيقية ، ولكن انظر إلى أي شيء يعمل بشكل أفضل لك.

لاحظ أيضًا نوع xor متغير كما int. في الواقع ، لا يوجد مشغل XOR محدد لـ byte القيم ، وإذا صنعت xor أ byte سيظل يجمع بسبب طبيعة مشغلي المهام المركبة ، ولكنه سيؤدي أداءً على كل تكرار - على الأقل في IL. من الممكن تمامًا أن تعتني JIT بهذا ، لكن ليست هناك حاجة حتى إلى طلب ذلك :)

Answer 2

من المحتمل أن تكون أسرع طريقة عبارة عن طاولة بحث 256 عنصرًا ...

int[] lut
{
    /*0x00*/ 0,
    /*0x01*/ 1,
    /*0x02*/ 1,
    /*0x03*/ 2
    ...
    /*0xFE*/ 7,
    /*0xFF*/ 8
}

على سبيل المثال

11110000^01010101 = 10100101 -> lut[165] == 4

Answer 3

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

من الناحية النظرية ، يمكن لـ Microsoft إضافة ملف BitArray.CountSetBits الوظيفة التي تحصل على جائزة مع أفضل خوارزمية لعمارة وحدة المعالجة المركزية تلك. أنا ، لأحد ، أرحب بمثل هذه الإضافة.

Answer 4

كما فهمت ذلك ، فأنت تريد تلخيص أجزاء كل XOR بين البايتات اليسرى واليمين.

for (int b = 0; b < left.Length; b++) {
  int num = left[b] ^ right[b];
  int sum = 0;

  for (int i = 0; i < 8; i++) {
    sum += (num >> i) & 1;
  }

   // do something with sum maybe?
}

Answer 5

لست متأكدًا مما إذا كنت تعني أن تم جمع البايتات أو البتات. لتلخيص البتات داخل بايت ، يجب أن يعمل هذا:

int nSum = 0;
for (int i=0; i<=7; i++)
{
   nSum += (byte_val>>i) & 1;
}

ستحتاج بعد ذلك إلى Xoring ، وحلق الصفيف حول هذا ، بالطبع.

Answer 6

يجب أن يفعل ما يلي

int BitXorAndSum(byte[] left, byte[] right) {
  int sum = 0;
  for ( var i = 0; i < left.Length; i++) { 
    sum += SumBits((byte)(left[i] ^ right[i]));
  }
  return sum;
}

int SumBits(byte b) {
  var sum = 0;
  for (var i = 0; i < 8; i++) {
    sum += (0x1) & (b >> i);
  }
  return sum;
}

Answer 7

يمكن إعادة كتابتها باسم ulong والاستخدام unsafe مؤشر ، لكن byte من الأسهل فهم:

static int BitCount(byte num)
{
    // 0x5 = 0101 (bit) 0x55 = 01010101
    // 0x3 = 0011 (bit) 0x33 = 00110011
    // 0xF = 1111 (bit) 0x0F = 00001111
    uint count = num;
    count = ((count >> 1) & 0x55) + (count & 0x55);
    count = ((count >> 2) & 0x33) + (count & 0x33);
    count = ((count >> 4) & 0xF0) + (count & 0x0F);
    return (int)count;
}

Answer 8

يمكن أن تبدو وظيفة عامة لحساب البتات:

int Count1(byte[] a)
{
  int count = 0;
  for (int i = 0; i < a.Length; i++)
  {
    byte b = a[i];
    while (b != 0)
    {
      count++;
      b = (byte)((int)b & (int)(b - 1));
    }
  }
  return count;
}

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

يمكن بعد ذلك حل مشكلتك باستخدام هذا:

int Count1Xor(byte[] a1, byte[] a2)
{
  int count = 0;
  for (int i = 0; i < Math.Min(a1.Length, a2.Length); i++)
  {
    byte b = (byte)((int)a1[i] ^ (int)a2[i]);
    while (b != 0)
    {
      count++;
      b = (byte)((int)b & (int)(b - 1));
    }
  }
  return count;
}

Answer 9

يجب أن يكون جدول البحث هو الأسرع ، ولكن إذا كنت ترغب في القيام بذلك بدون جدول بحث ، فسيعمل هذا على البايتات في 10 عمليات فقط.

public static int BitCount(byte value) {
    int v = value - ((value >> 1) & 0x55);
    v = (v & 0x33) + ((v >> 2) & 0x33);
    return ((v + (v >> 4) & 0x0F));
}

هذه نسخة بايت من وظيفة العد العامة الموصوفة في موقع شون إيرون أندرسون البطيء.