معالجة البتات والتلاعب بها في ++C

تصفير البت الأيمن (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;