تصفير البت الأيمن (Rightmost set bit)
ملاحظة: المقصود بتصفير بت أي جعل قيمته 0، والمقصود بتعيين قيمة بت أي جعل قيمته 1.
معالجة البتات وفق أسلوب لغة C
template < typename T > T rightmostSetBitRemoved(T n) { // وما بعدها c++11 لأجل // static_assert(std::is_integral<T>::value && !std::is_signed<T>::value, "type should //be unsigned"); return n & (n - 1); }
تفسير المثال
-
إذا كان
nيساوي الصفر، فسنحصل على0 & 0xFF..FFوالتي تساوي صفرًا. -
وإن كان غير ذلك فيمكن كتابة
nعلى الصورة0bxxxxxx10..00، ومن ثم سيُكتبn - 1على الصورة0bxxxxxx011..11. وهكذا، فإنّn & (n - 1)ستساوي0bxxxxxx000..00.
ضبط كل البتات إلى القيمة 1 (Set all bits)
معالجة البتات وفق أسلوب لغة C
x = -1; // -1 == 1111 1111 ... 1111b
(انظر هذه الصفحة الأجنبية للمزيد من التفاصيل).
استخدام std::bitset
std::bitset<10> x; x.set(); // إسناد القيمة 1 إلى كل البتات
تبديل قيمة بت
معالجة البتات وفق أسلوب لغة C
يمكن تبديل قيمة البت باستخدام معامِل XOR الثنائي (^) .
// عكس قيمتها الحالية x ستصبح قيمة البت. number ^= 1LL << x;
استخدام std::bitset
std::bitset<4> num(std::string("0100")); num.flip(2); // num = 0000 num.flip(0); // num = 0001 num.flip(); // يبدل جميع البتّات ،num = 1110
التحقق من قيمة البت
معالجة البتات وفق أسلوب لغة C
يمكن الحصول على قيمة بت معيّنة في التمثيل الثنائي لعدد ما عن طريق إزاحته إلى اليمين بمقدار x - إذ x تشير إلى عدد المرات-، ثم تنفيذ عملية AND الثنائية & عليه:
(number >> x) & 1LL; // تساوي 1، وإلا فسَيساوي 0 x الناتج سيساوي 1 في حال كانت البت رقم
يمكن تنفيذ عملية الإزاحة اليمينية (right-shift operation) إما كإزاحة حسابية مُؤشرَّة (arithmetic signed shift) أو كإزاحة منطقية غير مؤشرة (logical unsigned shift). إن كان number في التعبير number >> x ذا نوعٍ مُؤشَّر (signed type) وله قيمة سالبة، فإنّ القيمة الناتجة تحدد وفق التطبيق (implementation-defined).
وإن أردنا الحصول على قيمة تلك البت مباشرة في موضعها فيمكننا إزاحة القناع لليسار:
(number & (1LL << x));
الناتج سيساوي 1 >> x في حال كان البت رقم 1 يساوي 1 وإلا فسيساوي الصفر. يمكننا استخدامهما كشرط لأنّ جميع القيم المخالفة للصفر تُعدُّ صحيحة.
استخدام std::bitset
std::bitset<4> num(std::string("0010")); bool bit_val = num.test(1); // true تساوي bit_val قيمة
عدّ البتات ذات القيمة 1
تزيد الحاجة لعد البتات الموجودة في سلسلة بتية (Bitstring) في علم التشفير وغيره، وقد دُرست تلك المشكلة على نطاق واسع، والطريقة البسيطة لعدها هي المرور على البتات فرادى:
// n مراكمة العدد الإجمالي للوحدات في التمثيل الثنائي للعدد unsigned value = 1234; unsigned bits = 0; for (bits = 0; value; value >>= 1) bits += value & 1;
بيْد أنّ هذه الطريقة أفضل (تعتمد على إزالة البت الأيمن ذا القيمة 1):
// n تراكم إجمالي عدد البتّات في التمثيل الثنائي للعدد unsigned bits = 0; for (; value; ++bits) value &= value - 1;
تُنفِّذ الشيفرة أعلاه عددًا من التكرارات يكافئ عدد البتات التي تأخذ القيمة 1، لذا فهي مناسبة إن كان في value عدد قليل من البتات غير الصفرية (non-zero bits).
تم اقتراح هذه الطريقة للمرة الأولى من طرف بيتر فيجنيور (Peter Wegner) في عام CACM 3/322 - 1960، وقد لقيت قبولًا وتبنيًا كثيرًا منذ ظهورها في كتاب لغة البرمجة C الذي كتبه برايان كرنيجن ودينيس ريتشي. وتتطلب تلك الطريقة 12 عملية حسابية، إحداها عملية متعددة:
unsigned popcount(std::uint64_t x) { const std::uint64_t m1 = 0x5555555555555555; // binary: 0101... const std::uint64_t m2 = 0x3333333333333333; // binary: 00110011.. const std::uint64_t m4 = 0x0f0f0f0f0f0f0f0f; // binary: 0000111100001111 // وضع تعداد كل بتّيْن في هاتين البتّيْن x -= (x >> 1) & m1; // وضع تعداد كل 4 بتات في تلك البتات الأربعة x = (x & m2) + ((x >> 2) & m2); // وضع تعداد كل 8 بتات في تلك البتات الثمانية x = (x + (x >> 4)) & m4; // ... + (x<<24) + (x<<16) + (x<<8) + x البتات الثمانية على يسار return (x * h01) >> 56; }
هذا النوع من التطبيق لديه أفضل سلوك للحالة الأسوأ (Worst-Case) انظر Hamming weight لمزيد من التفاصيل. يحتوي العديد من وحدات المعالجة المركزية CPUs على تعليمات محددة (مثل popcnt في x86)، ويمكن للمصرّف إنشاء دالة مخصصة (غير قياسية) مضمنة، فمثلًا في مصرّف ++g نجد التعليمة التالية:
int __builtin_popcount (unsigned x);
التحقق مما إذا كان عدد صحيح ما هو أس للعدد 2
تُعد طريقة n & (n - 1) المُستعملة في مقالة إزالة بت التعيين اليمنى مفيدة لتحديد ما إذا كان عدد صحيح هو أس للرقم 2:
bool power_of_2 = n && !(n & (n - 1));
لاحظ أنه بدون الجزء الأول من عملية التحقق (n &&)، فسيُعد العدد 0 أسًّا للرقم 2، وذلك خطأ.
تعيين بت محدَّد
معالجة البتات وفق أسلوب لغة C
يمكن تعيين قيمة بت باستخدام عامل OR الثنائي (|).
// x تعيين قيمة البت رقم number |= 1LL << x;
استخدام std::bitset
التعبير set(x) أو set (x, true) يُسنِد القيمة 1 إلى البت الموجودة في الموضع x.
std::bitset<5> num(std::string("01100")); num.set(0); // num = 01101 num.set(2); // 01101 يساوي num لا يزال num.set(4,true); // 11110 يساوي الآن num
تصفير بت محدَّد
معالجة البتات وفق مقاربة لغة C
يمكن تصفير (إعطاء القيمة 0) بت محدَّد باستخدام معامِل AND الثنائي (&).
// x مسح البت الموجودة عند الموضع number &= ~(1LL << x);
استخدام std::bitset
تصفر التعليمة reset(x) أو set (x, false)) يمسح البت الموجودة في الموضع x.
std::bitset<5> num(std::string("01100")); num.reset(2); // 01000 يساوي الآن num num.reset(0); // 01000 يساوي الآن num num.set(3,false); // 00000 يساوي الآن num
تغيير قيمة البت رقم n إلى x
معالجة البتات وفق أسلوب لغة C
في المثال التالي، ستضبط قيمة البت رقم n إلى القيمة 1 في حال كانت قيمة x تساوي 1 وستُصفَّر قيمتها في حال كانت قيمة x يساوي الصفر:
number ^= (-x ^ number) & (1LL << n);
استخدام std::bitset
تعين التعليمة set(n,val) يعين القيمة val للبتّة n.
std::bitset<5> num(std::string("00100")); num.set(0,true); // 00101 يساوي الآن num num.set(2,false); // 00001 يساوي الآن num
تطبيق على معالجة البتات: تغيير حالة الحروف
أحد التطبيقات على معالجة البتات والتلاعب بها هو تحويل الحروف الأجنبية من الحالة الصغرى (Small) إلى الحالة الكبرى (Capital) أو العكس، عن طريق اختيار قناع (mask) و عملية ثنائية (bit operation) مناسبة. فمثلًا، يكون التمثيل الثنائي للحرف a هو 01(1)00001، وللحرف A هو 01(0)00001. لا يختلف التمثيلان السابقان إلا في البت الموجودة بين القوسين. لذا فإنّ تحويل الحرف a من الحالة الصغرى إلى الحالة الكبرى يكافئ تعيين البت الموجودة بين قوسين على القيمة 1 على النحو التالي:
/****************************************
تكبير حرف صغير
========================================
a: 01100001
mask: 11011111 <-- (0xDF) 11(0)11111
:---------
a&mask: 01000001 <-- A الحرف
*****************************************/
شيفرة تكبير الحرف A هي:
#include <cstdio> int main() { char op1 = 'a'; // "a" الحرف int mask = 0xDF; // اختيار قناع مناسب printf("a (AND) mask = A\n"); printf("%c & 0xDF = %c\n", op1, op1 & mask); return 0; }
النتيجة:
$ g++ main.cpp -o test1 $ ./test1 a (AND) mask = A a & 0xDF = A
حقول البتات
تحزِّم حقولُ البتات (Bit fields) بُنيات C و C++ لتصغير حجمها، إذ تحدد عدد البتات المخصصة لأعضاء البنية، ثم يدمج المصرّف (co-mingle) البتّات. السيء في هذا هو أنك لن تستطيع تحديد عنوان حقل البتة الخاص بعضو معين من البنية لأن المصرّف يدمجهما معًا. كذلك فإن الدالة sizeof() غير مسموح بها.
أحد الجوانب السلبية الأخرى، هو أنّ الدخول إلى حقول البتات بطيء بسبب الحاجة لاسترجاع الذاكرة ثم تطبيق العمليات الثنائية لاستخراج أو تعديل قيم الأعضاء. قد تزيد هذه العمليات أيضًا في حجم البرنامج التنفيذي (executable).
إليك المثال التالي لتوضيح كيفية التصريح والاستخدام:
struct FileAttributes { unsigned int ReadOnly: 1; unsigned int Hidden: 1; };
في هذا المثال، سيشغل كلّ حقل من هذين الحقلين بتّة واحدة في الذاكرة، وعلامة ذلك العدد 1 الموجود بعد أسماء المتغيّرات.
يمكن أن يكون حقل البتات من أيّ نوع عددي صحيح (من 8-bit int وحتى 64-bit int). يُستحسن استخدام النوع unsigned، وإلا فقد تحصل على نتائج غير متوقعة. إذا كانت هناك حاجة إلى المزيد من البتات، فاستبدل "1" بعدد البتات المطلوب. مثلًا:
struct Date { unsigned int Year: 13; // 2^13 = 8192 unsigned int Month: 4; // 2^4 = 16 unsigned int Day: 5; // 32 };
البنية بأكملها لن تستخدم إلا 22 بت فقط، وفي إعدادات التصريف العادية، سيكون ناتج sizeof الخاص بهذه البنية هو 4 بايتات. استخدام حقول البتات سهل جدّا، فما عليك إلا التصريح عن المتغيّر ثم استخدامه كبنية عادية.
Date d; d.Year = 2016; d.Month = 7; d.Day = 22; std::cout << "Year:" << d.Year << std::endl << "Month:" << d.Month << std::endl << "Day:" << d.Day << std::endl;
هذا الدرس جزء من سلسلة دروس عن C++.
ترجمة -وبتصرّف- للفصل Chapter 6: Bit Manipulation من كتاب C++ Notes for Professionals
أفضل التعليقات
لا توجد أية تعليقات بعد
انضم إلى النقاش
يمكنك أن تنشر الآن وتسجل لاحقًا. إذا كان لديك حساب، فسجل الدخول الآن لتنشر باسم حسابك.