ما هي عوامل تحويل البت (bit-shift) وكيف تعمل؟

Question

لقد كنت أحاول تعلم لغة C في أوقات فراغي، واللغات الأخرى (C#، Java، وما إلى ذلك) لها نفس المفهوم (وغالبًا نفس العوامل) ...

ما أتساءل عنه هو، على المستوى الأساسي، ما الذي يفعله تحويل البت (<<, >>, >>>) هل ما هي المشاكل التي يمكن أن يساعد في حلها، وما هي المشاكل الكامنة حول المنعطف؟وبعبارة أخرى، دليل المبتدئين المطلق لتحويل البت بكل ما فيه من خير.

Answer 1

يقوم مشغلو نقل البتات بما يوحي به اسمهم بالضبط.إنهم يغيرون البتات.فيما يلي مقدمة مختصرة (أو غير مختصرة) لمشغلي الورديات المختلفين.

المشغلين

• >> هو عامل التحول الحسابي (أو الموقع) لليمين.
• >>> هو عامل التحول الأيمن المنطقي (أو غير الموقع).
• << هو عامل التحول الأيسر، ويلبي احتياجات كل من التحولات المنطقية والحسابية.

يمكن تطبيق كل هذه العوامل على القيم الصحيحة (int, long, ربما short و byte أو char).في بعض اللغات، يتم تطبيق عوامل النقل على أي نوع بيانات أصغر من int يقوم بتغيير حجم المعامل تلقائيًا ليكون int.

لاحظ أن <<< ليس مشغلا، لأنه سيكون زائدا عن الحاجة.لاحظ أيضًا أن C وC++ لا يميزان بين عوامل التحويل الصحيحة.أنها توفر فقط >> عامل التشغيل، وسلوك التحول إلى اليمين هو التنفيذ المحدد للأنواع الموقعة.

---

التحول الأيسر (<<)

يتم تخزين الأعداد الصحيحة في الذاكرة كسلسلة من البتات.على سبيل المثال، تم تخزين الرقم 6 على هيئة 32 بت int سيكون:

00000000 00000000 00000000 00000110

نقل نمط البت هذا إلى الموضع الأيسر (6 << 1) سيؤدي إلى الرقم 12:

00000000 00000000 00000000 00001100

كما ترون، تم إزاحة الأرقام إلى اليسار بمقدار موضع واحد، والرقم الأخير على اليمين مليء بالصفر.قد تلاحظ أيضًا أن التحول إلى اليسار يعادل الضرب في قوى العدد 2.لذا 6 << 1 يعادل 6 * 2, ، و 6 << 3 يعادل 6 * 8.سيستبدل المترجم الأمثل الجيد الضرب بالتحولات عندما يكون ذلك ممكنًا.

التحول غير الدائري

يرجى ملاحظة أن هذه هي لا التحولات الدائرية.إزاحة هذه القيمة إلى اليسار بمقدار موضع واحد (3,758,096,384 << 1):

11100000 00000000 00000000 00000000

النتائج في 3,221,225,472:

11000000 00000000 00000000 00000000

يتم فقدان الرقم الذي يتم إزاحته "من النهاية".لا يلتف حولها.

---

التحول المنطقي لليمين (>>>)

التحول المنطقي لليمين هو العكس للتحول الأيسر.بدلًا من تحريك البتات إلى اليسار، فإنها تتحرك ببساطة إلى اليمين.على سبيل المثال، تحويل الرقم 12:

00000000 00000000 00000000 00001100

إلى اليمين بموضع واحد (12 >>> 1) سوف نعود لدينا الأصلي 6:

00000000 00000000 00000000 00000110

لذلك نرى أن الانتقال إلى اليمين يعادل القسمة على قوى 2.

لقد ولت القطع المفقودة

ومع ذلك، لا يمكن للإزاحة استعادة البتات "المفقودة".على سبيل المثال، إذا قمنا بتغيير هذا النمط:

00111000 00000000 00000000 00000110

إلى اليسار 4 وظائف (939,524,102 << 4) ، نحصل على 2,147,483,744:

10000000 00000000 00000000 01100000

ومن ثم العودة مرة أخرى ((939,524,102 << 4) >>> 4) نحصل على 134,217,734:

00001000 00000000 00000000 00000110

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

---

التحول الحسابي لليمين (>>)

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

على سبيل المثال، إذا قمنا بتفسير نمط البت هذا كرقم سالب:

10000000 00000000 00000000 01100000

لدينا الرقم -2,147,483,552.إن تحويل هذا إلى المواضع الأربعة الصحيحة مع التحول الحسابي (-2,147,483,552 >> 4) سيعطينا:

11111000 00000000 00000000 00000110

أو الرقم -134,217,722.

ومن ثم نرى أننا حافظنا على إشارة الأعداد السالبة باستخدام الإزاحة الحسابية لليمين، بدلًا من الإزاحة المنطقية لليمين.ومرة أخرى، نرى أننا نقوم بالقسمة على قوى العدد 2.

Answer 2

لنفترض أن لدينا بايت واحد:

0110110

إن تطبيق تغيير بت واحد لليسار يحصل على ما يلي:

1101100

تم نقل الصفر الموجود في أقصى اليسار خارج البايت، وتم إلحاق صفر جديد بالطرف الأيمن من البايت.

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

التحول إلى اليسار بمقدار N يعادل الضرب في 2^ن.

التحول لليمين بمقدار N هو (إذا كنت تستخدم تكملة تلك) هو ما يعادل القسمة على 2^ن والتقريب إلى الصفر.

يمكن استخدام Bitshifting لإجراء الضرب والقسمة بسرعة جنونية، بشرط أن تعمل بقوة 2.تستخدم جميع إجراءات الرسومات ذات المستوى المنخفض تقريبًا تقنية النقل بالبت.

على سبيل المثال، في الأيام الخوالي، استخدمنا الوضع 13h (320x200 256 لونًا) للألعاب.في الوضع 13h، تم وضع ذاكرة الفيديو بشكل تسلسلي لكل بكسل.وهذا يعني أنه لحساب موقع البكسل، يمكنك استخدام العمليات الحسابية التالية:

memoryOffset = (row * 320) + column

الآن، في ذلك اليوم وهذا العصر، كانت السرعة أمرًا بالغ الأهمية، لذلك كنا نستخدم التحولات الجزئية للقيام بهذه العملية.

ومع ذلك، 320 ليس من قوة العدد اثنين، لذا للتغلب على ذلك علينا معرفة ما هي قوة العدد اثنين التي إذا جمعناها معًا نحصل على 320:

(row * 320) = (row * 256) + (row * 64)

الآن يمكننا تحويل ذلك إلى التحولات اليسرى:

(row * 320) = (row << 8) + (row << 6)

للحصول على النتيجة النهائية:

memoryOffset = ((row << 8) + (row << 6)) + column

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

mov ax, 320; 2 cycles
mul word [row]; 22 CPU Cycles
mov di,ax; 2 cycles
add di, [column]; 2 cycles
; di = [row]*320 + [column]

; 16-bit addressing mode limitations:
; [di] is a valid addressing mode, but [ax] isn't, otherwise we could skip the last mov

المجموع:28 دورة على أي وحدة معالجة مركزية قديمة كانت بها هذه التوقيتات.

مقابل

mov ax, [row]; 2 cycles
mov di, ax; 2
shl ax, 6;  2
shl di, 8;  2
add di, ax; 2    (320 = 256+64)
add di, [column]; 2
; di = [row]*(256+64) + [column]

12 دورة على نفس وحدة المعالجة المركزية القديمة.

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

في وضع 32 أو 64 بت، يصبح كلا الإصدارين أقصر وأسرع كثيرًا.وحدات المعالجة المركزية الحديثة للتنفيذ خارج الترتيب مثل Intel Skylake (انظر http://agner.org/optimize/) تحتوي على تكاثر سريع جدًا للأجهزة (زمن وصول منخفض وإنتاجية عالية)، وبالتالي يكون الكسب أصغر بكثير.تعد عائلة AMD Bulldozer أبطأ قليلاً، خاصة بالنسبة لمضاعفة 64 بت.في وحدات المعالجة المركزية Intel وAMD Ryzen، يكون زمن الاستجابة أقل قليلاً ولكن تعليمات أكثر من المضاعفة (مما قد يؤدي إلى انخفاض الإنتاجية):

imul edi, [row], 320    ; 3 cycle latency from [row] being ready
add  edi, [column]      ; 1 cycle latency (from [column] and edi being ready).
; edi = [row]*(256+64) + [column],  in 4 cycles from [row] being ready.

ضد.

mov edi, [row]
shl edi, 6               ; row*64.   1 cycle latency
lea edi, [edi + edi*4]   ; row*(64 + 64*4).  1 cycle latency
add edi, [column]        ; 1 cycle latency from edi and [column] both being ready
; edi = [row]*(256+64) + [column],  in 3 cycles from [row] being ready.

سيقوم المترجمون بذلك نيابةً عنك:أنظر كيف تستخدم كل من gcc و clang و MSVC جميعها Shift+lea عند التحسين return 320*row + col;.

الشيء الأكثر إثارة للاهتمام الذي يجب ملاحظته هنا هو ذلك يحتوي الإصدار x86 على تعليمات النقل والإضافة (LEA) يمكنها القيام بتحولات صغيرة إلى اليسار والإضافة في نفس الوقت، مع الأداء مثل و add تعليمات.ARM أقوى:يمكن تحريك مُعامل واحد لأي تعليمات إلى اليسار أو اليمين مجانًا.لذا فإن القياس بواسطة ثابت وقت الترجمة المعروف بأنه أس 2 يمكن أن يكون أكثر كفاءة من الضرب.

---

حسنًا ، عد إلى العصر الحديث ...الشيء الأكثر فائدة الآن هو استخدام النقل الجزئي لتخزين قيمتين 8 بت في عدد صحيح 16 بت.على سبيل المثال، في C#:

// Byte1: 11110000
// Byte2: 00001111

Int16 value = ((byte)(Byte1 >> 8) | Byte2));

// value = 000011111110000;

في C++، يجب على المترجمين القيام بذلك نيابةً عنك إذا كنت تستخدم ملف struct مع عضوين 8 بت، ولكن في الواقع ليس دائمًا.

Answer 3

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

مثال حقيقي بسيط في برمجة الرسومات هو أن البكسل 16 بت يتم تمثيله على النحو التالي:

  bit | 15| 14| 13| 12| 11| 10| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1  | 0 |
      |       Blue        |         Green         |       Red          |

للحصول على القيمة الخضراء يمكنك القيام بذلك:

 #define GREEN_MASK  0x7E0
 #define GREEN_OFFSET  5

 // Read green
 uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

توضيح

من أجل الحصول على قيمة اللون الأخضر فقط، والتي تبدأ عند الإزاحة 5 وتنتهي عند 10 (أي.6 بتات طويلة)، تحتاج إلى استخدام قناع (بت)، والذي عند تطبيقه على بكسل 16 بت بأكمله، سينتج فقط البتات التي نهتم بها.

#define GREEN_MASK  0x7E0

القناع المناسب هو 0x7E0 وهو بالنظام الثنائي 000001111100000 (وهو 2016 بالنظام العشري).

uint16_t green = (pixel & GREEN_MASK) ...;

لتطبيق قناع، يمكنك استخدام عامل التشغيل AND (&).

uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

بعد تطبيق القناع، سينتهي بك الأمر برقم 16 بت وهو في الحقيقة مجرد رقم 11 بت نظرًا لأن MSB الخاص به موجود في 11 بت.يبلغ طول اللون الأخضر في الواقع 6 بتات فقط، لذا نحتاج إلى تصغيره باستخدام الإزاحة اليمنى (11 - 6 = 5)، وبالتالي استخدام 5 كإزاحة (#define GREEN_OFFSET 5).

من الشائع أيضًا استخدام إزاحات البت للضرب والقسمة السريعين على قوى العدد 2:

 i <<= x;  // i *= 2^x;
 i >>= y;  // i /= 2^y;

Answer 4

إخفاء البتات والتحويل

غالبًا ما يُستخدم تبديل البت في برمجة الرسومات ذات المستوى المنخفض.على سبيل المثال، قيمة لون بكسل معينة مشفرة بكلمة 32 بت.

 Pixel-Color Value in Hex:    B9B9B900
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

من أجل فهم أفضل، تم تصنيف نفس القيمة الثنائية مع الأقسام التي تمثل أي جزء من اللون.

                                 Red     Green     Blue       Alpha
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

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

قناعنا:

                  Red      Green      Blue      Alpha
 color :        10111001  10111001  10111001  00000000
 green_mask  :  00000000  11111111  00000000  00000000

 masked_color = color & green_mask

 masked_color:  00000000  10111001  00000000  00000000

المنطقي & يضمن المشغل الاحتفاظ بالقيم التي يكون فيها القناع 1 فقط.آخر شيء يتعين علينا فعله الآن هو الحصول على القيمة الصحيحة للعدد الصحيح عن طريق إزاحة كل تلك البتات إلى اليمين بمقدار 16 مكانًا (التحول المنطقي لليمين).

 green_value = masked_color >>> 16

وها هو، لدينا العدد الصحيح الذي يمثل مقدار اللون الأخضر في لون البكسل:

 Pixels-Green Value in Hex:     000000B9
 Pixels-Green Value in Binary:  00000000 00000000 00000000 10111001 
 Pixels-Green Value in Decimal: 185

يُستخدم هذا غالبًا لتشفير أو فك تشفير تنسيقات الصور مثل jpg,png,....

Answer 5

أحد الأمور المزعجة هو أن ما يلي يعتمد على التنفيذ (وفقًا لمعايير ANSI):

char x = -1;
x >> 1;

يمكن أن يكون x الآن 127 (01111111) أو لا يزال -1 (11111111).

في الممارسة العملية، عادة ما يكون هذا هو الأخير.

Answer 6

أنا أكتب النصائح والحيل فقط، قد تجدها مفيدة في الاختبارات/الامتحانات.

1. n = n*2: n = n<<1
2. n = n/2: n = n>>1
3. التحقق مما إذا كانت n هي قوة 2 (1،2،4،8، ...):يفحص !(n & (n-1))
4. الحصول س^ذ قليل من n: n |= (1 << x)
5. التحقق مما إذا كانت x زوجية أم فردية: x&1 == 0 (حتى)
6. تبديل ن^ذ قليلا من x: x ^ (1<<n)

Answer 7

لاحظ أنه في تطبيق Java، يتم تعديل عدد البتات المراد إزاحتها حسب حجم المصدر.

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

(long) 4 >> 65

يساوي 2.قد تتوقع أن يؤدي تحويل البتات إلى اليمين 65 مرة إلى صفر كل شيء، ولكنه في الواقع يعادل:

(long) 4 >> (65 % 64)

وهذا ينطبق على <<، >>، و >>>.لم أجربه بلغات أخرى.

Answer 8

بعض العمليات/التلاعبات المفيدة في لغة بايثون.تم تنفيذ إجاباتRavi Prakash في بيثون.

# basic bit operations
# int to bin
print(bin(10))

# bin to int
print(int('1010',2))

# multiplying x with 2 .... x**2== x << 1
print(200<<1)

# dividing x with 2 .... x /2 == x >> 1
print(200>>1)

# modulo x with 2 .... x%2 == x&1
if 20&1==0:
    print("20 is a even number")

# check if n is power of 2 : check !(n & (n-1))
print(not(33 &(33-1)))

# getting xth bit of n : (n>>x)&1
print((10>>2)&1) # bin of 10==1010 and 2nd bit is 0

# toggle nth bit of x : x^(1<<n)
# take bin(10)==1010 and toggling 2nd bit in bin(10) we get 1110 === bin(14)
print(10^(1<<2)) 

Answer 9

انتبه إلى أن الإصدار 32 بت فقط من PHP متوفر على نظام التشغيل Windows.

ثم إذا قمت على سبيل المثال بإزاحة << أو >> أكثر من 31 بت، فستكون النتائج غير متوقعة.عادةً ما يتم إرجاع الرقم الأصلي بدلاً من الأصفار، وقد يكون ذلك خطأً صعبًا للغاية.

بالطبع إذا كنت تستخدم إصدار 64 بت من PHP (يونكس)، فيجب عليك تجنب التحول بأكثر من 63 بت.ومع ذلك، على سبيل المثال، يستخدم MySQL BIGINT 64 بت، لذلك لا ينبغي أن تكون هناك أي مشاكل في التوافق.

تحديث:من PHP7 Windows، أصبحت إصدارات php قادرة أخيرًا على استخدام الأعداد الصحيحة الكاملة 64 بت:يعتمد حجم العدد الصحيح على النظام الأساسي، على الرغم من أن القيمة القصوى التي تبلغ حوالي 2 مليار هي القيمة المعتادة (أي 32 بتة موقعة).عادةً ما يكون الحد الأقصى لقيمة الأنظمة الأساسية 64 بت حوالي 9E18، باستثناء نظام التشغيل Windows قبل PHP 7، حيث كان دائمًا 32 بت.