معالجة البتات

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

يستخدم الكود المصدري الذي يُجري عمليات معالجة البتات عمليات منطقية مثل: AND، OR، XOR، NOT، وربما عمليات أخرى مماثلة للمعاملات المنطقية. كما توجد عمليات إزاحة البتات ، وعمليات لحساب الآحاد والأصفار، وتحديد أعلى وأدنى قيمة للآحاد أو الأصفار، وتعيين البتات وإعادة ضبطها واختبارها، واستخراج الحقول وإدراجها، وإخفاء الحقول وتصفيرها، وتجميع البتات وتوزيعها من وإلى مواضع أو حقول محددة. ويمكن لمعاملات الحساب الصحيح أيضًا أن تُجري عمليات على البتات بالتزامن مع المعاملات الأخرى.

في بعض الحالات، يمكن أن تُغني معالجة البتات عن الحاجة إلى تكرار العمليات على بنية البيانات أو تُقلل منها، كما يمكن أن تُحقق تسريعًا كبيرًا، نظرًا لأن معالجة البتات تتم بالتوازي. مع ذلك، إذا كانت العملية غير مألوفة أو مكلفة التنفيذ، فلا يُمكن تبرير إدراجها، مما يُحفز إجراء بحوث مبتكرة. ^{[ 1 ]}

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

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

تُجرى عملية البت على نمط بت واحد أو أكثر أو على أرقام ثنائية على مستوى بتاتها الفردية . وهي عملية سريعة وبسيطة تدعمها وحدة المعالجة المركزية (CPU) بشكل مباشر، وتُستخدم لمعالجة القيم لأغراض المقارنة والحساب.

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

لتحديد ما إذا كان عدد ما قوة للعدد اثنين، يمكننا نظرياً إجراء عملية قسمة عدد صحيح على اثنين بشكل متكرر حتى يصبح العدد غير قابل للقسمة على 2 بشكل متساوٍ؛ إذا كان العامل الوحيد المتبقي هو 1، فإن العدد الأصلي كان قوة للعدد 2. باستخدام البتات والمعاملات المنطقية، توجد عبارة بسيطة تُرجع صحيح (1) أو خطأ (0):

bool isPowerOfTwo = ( x != 0 ) && (( x & ( x - 1 )) == 0 );

يستغل النصف الثاني حقيقة أن قوى العدد اثنين لها بت واحد فقط مضبوط في تمثيلها الثنائي:

x == 0...0 1 0...0 x-1 == 0...001...1 x & (x-1) == 0...000...0

إذا لم يكن العدد صفرًا ولا قوة من قوى العدد اثنين، فسيكون له الرقم '1' في أكثر من موضع:

x == 0... 1 ...0 1 0...0 x-1 == 0... 1 ...001...1 x & (x-1) == 0... 1 ...000...0

إذا تم استخدام كود لغة التجميع المضمن ، فقد تكون هناك تعليمة ( popcnt ) تحسب عدد الآحاد أو الأصفار في المعامل؛ المعامل الذي يحتوي على بت واحد فقط من النوع '1' هو قوة للعدد 2. ومع ذلك، قد يكون لهذه التعليمة زمن استجابة أكبر من طريقة البتات المذكورة أعلاه.

لا توفر المعالجات عادةً سوى مجموعة فرعية من عوامل التشغيل الثنائية المفيدة. لا تدعم لغات البرمجة معظم عمليات البت بشكل مباشر، لذا يجب استخدام أساليب برمجية خاصة بها. على سبيل المثال، توفر لغة البرمجة "C" فقط عمليات AND (&) وOR (|) وXOR (^) وNOT (~) على مستوى البت. بينما توفر لغة Fortran عمليات AND (.and.) وOR (.or.) وXOR (.neqv.) وEQV (.eqv.). عندما تتوفر المجموعة الكاملة من عوامل التشغيل الثنائية، فإنها تكون دوالًا منطقية ذات مُعاملين أو ثلاثة مُعاملات.

توفر لغة Algol وظائف استخراج وإدراج حقول البتات. عندما توفر اللغات عمليات بتات لا تتوافق مباشرة مع تعليمات الأجهزة، يجب على المترجمات توليد العملية من المعاملات المتاحة.

تُعدّ عملية عدّ الأصفار البادئة من العمليات المفيدة للغاية ، وتُستخدم للعثور على البت الأعلى المُفعّل في كلمة الآلة، مع العلم أنها قد تحمل أسماءً مختلفة باختلاف البنى. ^{[ 2 ]} لا يوجد مصطلح برمجة بسيط لهذه العملية، لذا يجب توفيرها من خلال دالة مُضمّنة في المُصرّف أو روتين مكتبة النظام. بدون هذه العملية، تُصبح أي عملية تتعلق بالبت الأعلى في الكلمة مُكلفة للغاية (انظر Find first set#CLZ )، وذلك بسبب عدم تناظر عملية نقل البيانات في العمليات الحسابية. لحسن الحظ، وفّرت معظم بنى المعالجات المركزية هذه العملية منذ منتصف ثمانينيات القرن الماضي. كما تُوفّر عادةً عملية مُصاحبة تُسمى عدّ الآحاد ، أو Popcount ، والتي تحسب عدد البتات المُفعّلة في كلمة الآلة، كعملية مُدمجة في الجهاز.

غالبًا ما يتم توفير عمليات البت الأبسط مثل تعيين البت وإعادة التعيين والاختبار والتبديل كعوامل تشغيل للأجهزة، ولكن يمكن محاكاتها بسهولة إذا لم تكن كذلك - على سبيل المثال (SET R0, 1; LSHFT R0, i; OR x, R0) يقوم بتعيين البت i في المعامل x.

تتضمن بعض عمليات البت الأكثر فائدة وتعقيدًا والتي يجب ترميزها كعبارات اصطلاحية في لغة البرمجة وتوليفها بواسطة المترجمات ما يلي:

• مسح من موضع البت المحدد إلى الأعلى (ترك الجزء السفلي من الكلمة)
• قم بمسح الجزء العلوي من الكلمة بدءًا من موضع البت المحدد نزولاً (اترك الجزء العلوي من الكلمة)
• قناع من البت الأدنى إلى الأسفل (مسح الكلمة الأدنى)
• قناع من البت الأعلى إلى الأعلى (مسح الكلمة السفلية)
• استخراج بتفيلد
• إدراج حقل البت
• عمليات تشتيت/تجميع حقول البتات التي توزع أجزاءً متجاورة من حقل بتات على كلمة الآلة، أو تجمع حقول بتات متباينة في الكلمة في جزء متجاور من حقل بتات (انظر عوامل تشغيل Intel PEXT/PDEP الحديثة). تُستخدم في التشفير وتشفير الفيديو.
• عكس المصفوفة

يمكن اختزال بعض العمليات الحسابية إلى عمليات أبسط وعمليات على مستوى البتات:

• اختزل عملية الضرب في ثابت إلى سلسلة من عمليات الإزاحة والجمع

على سبيل المثال، الضرب في 9 هو نسخ المعامل، ثم إزاحته لأعلى بمقدار 3 (الضرب في 8)، ثم إضافته إلى المعامل الأصلي.

• اختزل القسمة على ثابت إلى سلسلة من عمليات الإزاحة والطرح

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

تتضمن التعليمات غير العادية وحدات التحكم في ضغط الدم المعبأة (BCD) والتي تعتبر شائعة جدًا في الصناعات المالية والتجارية والصناعية.

• وارن، هنري س. (2013). متعة المخترق (  الطبعة الثانية). أديسون-ويسلي بروفيشنال. ص  512. ISBN 978-0321842688.
• كنوت، دونالد إي. (2009). فن برمجة الحاسوب ، المجلد 4، الجزء 1: حيل وتقنيات البتات؛ مخططات القرار الثنائي (  الطبعة الأولى). أديسون-ويسلي بروفيشنال. ص  272. ISBN 978-0321580504.( مسودة الجزء 1أ مؤرشفة بتاريخ 16-10-2019 على موقع Wayback Machine، وهي متاحة للتنزيل)

• أندرسون، شون إيرون، محرر. (26-11-2009) [1997]. "حيل تعديل البتات" . جامعة ستانفورد . مؤرشف من الأصل في 1-6-2020 . تم الاسترجاع في 1-6-2020 .
• حيل معالجة البتات مع شروحات كاملة وشفرة المصدر
• دليل Intel intrinsics
• xchg rax, rax : ألغاز واختراقات x86_64
• خوارزميات السحر التجميعي من جامعة كنتاكي