c++ - and - bitwise operators شرح




تحويل 0x1234 إلى 0x11223344 (9)

إليك محاولة أخرى ، باستخدام ثماني عمليات:

b = (((c & 0x0F0F) * 0x0101) & 0x00F000F) + 
    (((c & 0xF0F0) * 0x1010) & 0xF000F00);
b += b * 0x10;

printf("%x\n",b); //Shows '0x11223344'

* لاحظ أن هذا المنشور يحتوي في الأصل على رمز مختلف تمامًا ، استنادًا إلى بتات Interleave بواسطة Binary Magic Numbers من صفحة Bithacks من Sean Anderson. لكن ذلك لم يكن ما يطلبه البروتوكول الاختياري. لذلك فقد بن إزالتها. تشير غالبية التعليقات أدناه إلى تلك النسخة المفقودة .

كيف يمكنني توسيع الرقم الست عشري 0x1234 إلى 0x11223344 بطريقة عالية الأداء؟

unsigned int c = 0x1234, b;
b = (c & 0xff) << 4 | c & 0xf | (c & 0xff0) << 8
        | (c & 0xff00) << 12 | (c & 0xf000) << 16;
printf("%p -> %p\n", c, b);

انتاج:

0x1234 -> 0x11223344

أحتاج هذا لتحويل اللون. يقدم المستخدمون بياناتهم في النموذج 0xARGB ، وأحتاج إلى تحويلها إلى 0xAARRGGBB . ونعم ، يمكن أن يكون هناك ملايين ، لأن كل منها يمكن أن يكون بكسل. 1000 × 1000 بكسل يساوي مليون.

الحالة الفعلية أكثر تعقيدًا ، لأن قيمة 32 بت واحدة تحتوي على ألوان المقدمة والخلفية. أصبحت 0xARGBargb : [ 0xAARRGGBB, 0xaarrggbb ]

أوه نعم ، شيء واحد آخر ، في تطبيق حقيقي ، أنا أيضاً أبطل ألفا ، لأنه في OpenGL 0xFF غير شفاف و 0x00 هو الأكثر شفافية ، وهو غير مريح في معظم الحالات ، لأنه عادة ما تحتاج فقط إلى جزء RGB ويفترض أن الشفافية كن غير حاضر


لست متأكدًا من الطريقة الأكثر فاعلية ، لكن هذا أقصر قليلاً:

#include <stdio.h>

int main()
{
  unsigned x = 0x1234;

  x = (x << 8) | x;
  x = ((x & 0x00f000f0) << 4) | (x & 0x000f000f);
  x = (x << 4) | x;

  printf("0x1234 -> 0x%08x\n",x);

  return 0;
}

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

unsigned *makeLookupTable(void)
{
  unsigned *tbl = malloc(sizeof(unsigned) * 65536);
  if (!tbl) return NULL;
  int i;
  for (i = 0; i < 65536; i++) {
    unsigned x = i;
    x |= (x << 8);
    x = ((x & 0x00f000f0) << 4) | (x & 0x000f000f);
    x |= (x << 4);

    /* Uncomment next line to invert the high byte as mentioned in the edit. */
    /* x = x ^ 0xff000000; */

    tbl[i] = x;
  }
  return tbl;
}

بعد ذلك ، يكون كل تحويل مجرد شيء مثل:

result = lookuptable[input];

..أو ربما:

result = lookuptable[input & 0xffff];

أو يمكن استخدام جدول بحث أصغر أو أكثر ملاءمة للتخزين المؤقت (أو زوج) مع بحث واحد لكل من البايتات العالية والمنخفضة (كما لاحظ @ LưuVĩnhPhúc في التعليقات). في هذه الحالة ، قد يكون رمز إنشاء الجدول:

unsigned *makeLookupTableLow(void)
{
  unsigned *tbl = malloc(sizeof(unsigned) * 256);
  if (!tbl) return NULL;
  int i;
  for (i = 0; i < 256; i++) {
    unsigned x = i;
    x = ((x & 0xf0) << 4) | (x & 0x0f);
    x |= (x << 4);
    tbl[i] = x;
  }
  return tbl;
}

... والجدول الثاني اختياري:

unsigned *makeLookupTableHigh(void)
{
  unsigned *tbl = malloc(sizeof(unsigned) * 256);
  if (!tbl) return NULL;
  int i;
  for (i = 0; i < 256; i++) {
    unsigned x = i;
    x = ((x & 0xf0) << 20) | ((x & 0x0f) << 16);
    x |= (x << 4);

    /* uncomment next line to invert high byte */
    /* x = x ^ 0xff000000; */

    tbl[i] = x;
  }
  return tbl;
}

... ولتحويل قيمة مع جدولين:

result = hightable[input >> 8] | lowtable[input & 0xff];

... أو مع واحد (فقط الجدول المنخفض أعلاه):

result = (lowtable[input >> 8] << 16) | lowtable[input & 0xff];
result ^= 0xff000000; /* to invert high byte */

إذا لم يتغير الجزء العلوي من القيمة (alpha؟) كثيرًا ، فقد يؤدي الجدول الكبير المنفرد أداءً جيدًا نظرًا لأن عمليات البحث المتتالية ستكون أقرب في الجدول.

أخذت رمز اختبار الأداء الذي نشرهApriori ، وأجرت بعض التعديلات ، وأضفت اختبارات للردود الأخرى التي لم يدرجها في الأصل ... ثم جمعت ثلاثة إصدارات منها بإعدادات مختلفة. واحد هو رمز 64 بت مع تمكين SSE4.1 ، حيث يمكن للمترجم الاستفادة من SSE لتحسينات ... ثم نسختين 32 بت ، واحد مع SSE والآخر بدون. على الرغم من أن الثلاثة قد تم تشغيلهم على نفس المعالج الحديث إلى حد ما ، فإن النتائج تظهر كيف يمكن أن يتغير الحل الأمثل اعتمادًا على ميزات المعالج:

                           64b SSE4.1  32b SSE4.1  32b no SSE
-------------------------- ----------  ----------  ----------
ExpandOrig           time:  3.502 s     3.501 s     6.260 s
ExpandLookupSmall    time:  3.530 s     3.997 s     3.996 s
ExpandLookupLarge    time:  3.434 s     3.419 s     3.427 s
ExpandIsalamon       time:  3.654 s     3.673 s     8.870 s
ExpandIsalamonOpt    time:  3.784 s     3.720 s     8.719 s
ExpandChronoKitsune  time:  3.658 s     3.463 s     6.546 s
ExpandEvgenyKluev    time:  6.790 s     7.697 s    13.383 s
ExpandIammilind      time:  3.485 s     3.498 s     6.436 s
ExpandDmitri         time:  3.457 s     3.477 s     5.461 s
ExpandNitish712      time:  3.574 s     3.800 s     6.789 s
ExpandAdamLiss       time:  3.673 s     5.680 s     6.969 s
ExpandAShelly        time:  3.524 s     4.295 s     5.867 s
ExpandAShellyMulOp   time:  3.527 s     4.295 s     5.852 s
ExpandSSE4           time:  3.428 s
ExpandSSE4Unroll     time:  3.333 s
ExpandSSE2           time:  3.392 s
ExpandSSE2Unroll     time:  3.318 s
ExpandAShellySSE4    time:  3.392 s

تم تجميع الملفات التنفيذية على نظام التشغيل Linux 64 بت باستخدام gcc 4.8.1 ، باستخدام -m64 -O3 -march=core2 -msse4.1 و -m32 -O3 -march=core2 -msse4.1 و -m32 -O3 -march=core2 -mno-sse على التوالي. @ تم حذف اختبارات SSE الخاصة بـ Apriori للإنشاءات ذات 32 بت (تحطمت على 32 بت مع تمكين SSE ، ومن الواضح أنها لن تعمل مع تعطيل SSE).

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

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


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

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

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


إذا كان الضرب رخيصًا وكان الحساب 64 بت متاحًا ، فيمكنك استخدام هذا الرمز:

uint64_t x = 0x1234;
x *= 0x0001000100010001ull;
x &= 0xF0000F0000F0000Full;
x *= 0x0000001001001001ull;
x &= 0xF0F0F0F000000000ull;
x = (x >> 36) * 0x11;
std::cout << std::hex << x << '\n';

في الواقع ، فإنه يستخدم نفس الفكرة مثل المحاولة الأصلية لـ AShelly.


ربما هذا يمكن أن يكون أكثر بساطة وكفاءة.

unsigned int g = 0x1234;
unsigned int ans = 0;

ans = ( ( g & 0xf000 ) << 16) + ( (g & 0xf00 ) << 12)
    + ( ( g&0xf0 ) << 8) + ( ( g&0xf ) << 4);

ans  = ( ans | ans>>4 );

printf("%p -> %p\n", g, ans);

طريقة أخرى هي:

DWORD OrVal(DWORD & nible_pos, DWORD input_val, DWORD temp_val, int shift)
{
    if (nible_pos==0)
        nible_pos = 0x0000000F;
    else
        nible_pos = nible_pos << 4;
    DWORD nible = input_val & nible_pos;
    temp_val |= (nible << shift);
    temp_val |= (nible << (shift + 4));
    return temp_val;
}

DWORD Converter2(DWORD input_val)
{
    DWORD nible_pos = 0x00000000;
    DWORD temp_val = 0x00000000;
    temp_val = OrVal(nible_pos, input_val, temp_val, 0);
    temp_val = OrVal(nible_pos, input_val, temp_val, 4);
    temp_val = OrVal(nible_pos, input_val, temp_val, 8);
    temp_val = OrVal(nible_pos, input_val, temp_val, 12);
    return temp_val;
}

DWORD val2 = Converter2(0x1234);

نسخة محسنة (3 مرات أسرع):

DWORD Converter3(DWORD input_val)
{
    DWORD nible_pos = 0;
    DWORD temp_val = 0;
    int shift = 0;
    DWORD bit_nible[4] = { 0x000F, 0x000F0, 0x0F00, 0xF000 };

    for ( ; shift < 16; shift+=4 )
    {
        if (nible_pos==0)
            nible_pos = 0x0000000F;
        else
            nible_pos = nible_pos << 4;
        DWORD nible = input_val & nible_pos;
        temp_val |= (nible << shift);
        temp_val |= (nible << (shift + 4));
    }

    return temp_val;
}


أعتقد أن نهج جدول البحث الذي اقترحه Dmitri هو خيار جيد ، لكنني أقترح المضي قدمًا خطوة واحدة وإنشاء الجدول في وقت الترجمة ؛ القيام بالعمل في وقت الترجمة سوف يقلل بوضوح من وقت التنفيذ.

أولاً ، نقوم بإنشاء قيمة وقت الترجمة باستخدام أي من الطرق المقترحة:

constexpr unsigned int transform1(unsigned int x)
{
  return ((x << 8) | x);
}

constexpr unsigned int transform2(unsigned int x)
{
  return (((x & 0x00f000f0) << 4) | (x & 0x000f000f));
}

constexpr unsigned int transform3(unsigned int x)
{
  return ((x << 4) | x);
}

constexpr unsigned int transform(unsigned int x)
{
  return transform3(transform2(transform1(x)));
}

// Dimitri version, using constexprs
template <unsigned int argb> struct aarrggbb_dimitri
{
  static const unsigned int value = transform(argb);
};

// Adam Liss version
template <unsigned int argb> struct aarrggbb_adamLiss
{
  static const unsigned int value =
    (argb & 0xf000) * 0x11000 +
    (argb & 0x0f00) * 0x01100 +
    (argb & 0x00f0) * 0x00110 +
    (argb & 0x000f) * 0x00011;
};

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

#define EXPAND16(x) aarrggbb<x + 0>::value, \
aarrggbb<x + 1>::value, \
aarrggbb<x + 2>::value, \
aarrggbb<x + 3>::value, \
aarrggbb<x + 4>::value, \
aarrggbb<x + 5>::value, \
aarrggbb<x + 6>::value, \
... and so on

#define EXPAND EXPAND16(0), \
EXPAND16(0x10), \
EXPAND16(0x20), \
EXPAND16(0x30), \
EXPAND16(0x40), \
... and so on

... and so on

انظر التجريبي هنا .

ملاحظة: يمكن استخدام نهج Adam Liss بدون C ++ 11.


إذا كنت ستقوم بذلك من أجل OpenGL ، أقترح عليك استخدام glTexImageXDدالة مع typeتعيين المعلمة إلى GL_UNSIGNED_SHORT_4_4_4_4. يجب أن يقوم برنامج التشغيل OpenGL بالباقي. وحول انعكاس الشفافية يمكنك التلاعب دائما مزج عبر glBlendFuncو glBlendEquationظائف.


unsigned long transform(unsigned long n)
{

    /* n: 00AR
     *    00GB
     */
    n = ((n & 0xff00) << 8) | (n & 0x00ff);

    /* n: 0AR0
     *    0GB0
     */
    n <<= 4;

    /* n: AAR0
     *    GGB0
     */
    n |= (n & 0x0f000f00L) << 4;

    /* n: AARR
     *    GGBB
     */
    n |= (n & 0x00f000f0L) >> 4;

    return n;
}

يتم تحويل المكونات ألفا وحمراء إلى أعلى 2 بايت حيث ينتمون ، والنتيجة ثم تحولت إلى اليسار من 4 بت ، مما أدى إلى أن يكون كل مكون بالضبط حيث يجب أن يكون.

باستخدام نموذج 0AR0 0GB0 ، يتم استخدام قناع بت ومجموعة تركيبة لليسار مع القيمة الحالية هذا بنسخ المكونات A و G إلى الموضع الأيسر منها. يتم نفس الشيء بالنسبة لمكونات R و B ، إلا في الاتجاه المعاكس.





bit-manipulation