فهرست عناوین

آموزش ساده Bit Mask در ++C

این تکنیک برای مدیریت و عضو کردن یکسری عناصر به مجموعه‌ است. مجموعه در اینجا با عنوان رشته بیتی یاد می‌شود که هر بیت آن نشان دهنده‌ی وضعیتِ عنصر مورد نظر می‌باشد. اگر عنصر مورد نظر در مجموعه یا رشته بیتی عضو است، آنگاه بیت متناظر آن در رشته بیتی، شامل مقدار یک است، در غیر این صورت، این بیت صفر خواهد بود.

نکته: باید برای هر عنصر مجموعه، maskای را در نظر گرفته شود.

تا اینجا دو مولفه، به نام‌های رشته بیتی که همان مجموعه‌ است و mask که مربوط به هر عنصر مجموعه است اشاره شد.

در زیر چندین عملیات بیان می‌شود که می‌توان روی مجموعه یا رشته بیتی انجام داد؛ این عملیات‌ها با کمک عملگرهای بیتی انجام می‌پذیرد:

بررسی عضو بودن عنصر مورد نظر در رشته بیتی

منظور این هست که بررسی شود بیت متناظر با عنصر، دارای مقدار یک هست یا صفر؛ اگر مقدار صفر هست یعنی عنصر عضو مجموعه نیست و اگر بیت مربوطه مقدار یک است، یعنی عنصر عضو مجموعه است(با استفاده از عملگر منطقی &).

این عملیات به صورت زیر انجام می‌پذیرد:

(رشته بیتی) & (عنصر مورد نظر)

نکته: منظور از عنصر مورد نظر، مقدار mask آن می‌باشد.

اضافه کردن عنصر به مجموعه‌ یا رشته بیتی

منظور این هست که بیت متناظر با عنصر، در مجموعه یا رشته بیتی، دارای مقدار یک گردد(با استفاده از عملگر منطقی or).

(رشته بیتی) | (عنصر مورد نظر)

حذف عنصر از رشته بیتی

منظور این هست که بیت متناظر با عنصر، در مجموعه یا رشته بیتی، دارای مقدار صفر گردد(با استفاده از عملگر منطقی or و not).

(رشته بیتی) | (عنصر مورد نظر~)

نکته: علامت not یا معکوس به صورت ~ می‌باشد.

تغییر وضعیت عضو بودن عنصر مورد نظر

منظور این است که اگر مقدار بیت متناظر با عنصر در رشته بیتی، دارای مقدار یک بود، صفر گردد یعنی عنصر، از مجموعه حذف گردد و همچنین اگر مقدار بیت متناظر با عنصر، در رشته بیتی، صفر بود دارای مقدار یک گردد، یعنی عنصر به مجموعه اضافه شود. در اصطلاح به این نوع عملیات تغییر وضعیت، toggle گفته می شود (با استفاده از عملگر منطقی xor).

(رشته بیتی) ^ (عنصر مورد نظر)

یک مثال بسیار ساده و رایج

لیستی از افراد به صورت زیر وجود دارد:

Copy to Clipboard

در این لیست، فقط ALI، REZA و SAJJAD دانشجو هستند؛ می‌خواهیم مجموعه‌ای از دانشجویان را ایجاد نماییم و عملیات‌هایی مانند بررسی عضو بودن دانشجو در مجموعه، حذف دانشجو از مجموعه، عضو کردن دانشجوی جدید به مجموعه را، انجام دهیم:

در ابتدا لازم هست که مجموعه یا همان رشته بیتی که شامل دانشجویان هست را ایجاد نماییم:

Copy to Clipboard

در ادامه برای هر عنصر (افراد)، لازم است maskی ایجاد شود:

Copy to Clipboard

نکته: به طور کلی تعداد افراد با تعداد بیت‌ها، یکسان است و دلیل این امر به خاطر متمایز کردن افراد نسبت به یکدیگر می‌باشد (می‌توان به این صورت بیان کرد: به هر فرد یک ID یا شناسه منحصر به فرد، داده شده است).

نکته: مقدار 0b0001، عدد باینری (دودیی) را نشان می‌دهد.

عملیات عضو کردن دانشجو در مجموعه

Copy to Clipboard

اکنون مقدار listOfStudents ، عدد 11 می‌باشد که به صورت دودویی یا باینری عدد 1011 است که نشان دهنده‌ی عضو بودن سه دانشجو ALI، REZA و SAJJAD در مجموعه است (یعنی بیت‌های متناظر این افراد، یک می‌باشند).

سه خط کد بالا را می توان به صورت زیر خلاصه کرد:

Copy to Clipboard

عملیات حذف کردن دانشجو

Copy to Clipboard

اکنون مقدارlistOfStudents ، عدد 9 است که به صورت دودویی 1001 می‌باشد و نشان می‌دهد که کاربر REZA از مجموعه حذف گردیده است.

سوال) برای حذف کردن دو دانشجو، چه کدی باید نوشت؟

جواب) به عنوان نمونه برای حذف دانشجوهای ALI و REZA به صورت زیر باید اقدام کرد:

Copy to Clipboard

بررسی عضو بودن دانشجو در مجموعه

Copy to Clipboard

چون در عملیات قبلی دانشجوی REZA را حذف نمودیم، مقدار isExist، صفر می‌باشد.

Copy to Clipboard

مقدار isExist، یک می‌باشد و نشان از عضو بودن SAJJAD در مجموعه دانشجویان است.

نکته: در کتابخانه‌های استاندارد ++C ، کتابخانه‌ای با نام bitset برای تسهیل مدیریت و کار با تکنیک mask، وجود دارد.

کد مثال بالا

Copy to Clipboard

#include <iostream>
#include <string>
#include <vector>
using namespace std;
/**
* List of persons.
*
* these are bit masks.
*/
const int ALI                {0b1000};
const int MOHAMMAD        {0b0100};
const int REZA                {0b0010};
const int SAJJAD        {0b0001};
/**
* List of people by name.
*/
string nameOfPersons[] = {"ali", "hasan", "reza", "sajjad"};
vector<int> persons{ALI, MOHAMMAD, REZA, SAJJAD};
/**
* @class Students.
*/
class Students
{
public:
Students(int _listOfStudents)
{
listOfStudents |= _listOfStudents;
}
/**
* Shows the value of the bit string in binary. 
*
* shows the list of students in bits.
*/
string showStudents()
{
int sizeOfint = 32;
std::string binary_str = "";
for (int i = (sizeOfint -1); i >= 0; i--) {
int k = listOfStudents >> i;
if (k & 1)
binary_str.push_back('1');
else
binary_str.push_back('0');
}
return binary_str;
}
/**
* Shows the list of students by their names.
*/
string showStudentsName()
{
string nameOfStudents = "",
students = showStudents();
int len = students.size() - 1,
lenOfpersons = (sizeof(nameOfPersons) / sizeof(string)) - 1;
for (int i = len; i >= 0; lenOfpersons--, i--)
{
if (students[i] == '0')
continue;
if (! nameOfStudents.empty())
nameOfStudents += "-";
nameOfStudents += nameOfPersons[lenOfpersons];
}
return nameOfStudents;
}
int add(int student)
{
return listOfStudents |= student;
}
int destroy(int student)
{
return listOfStudents &= (~student);
}
bool isExist(int student)
{
return listOfStudents & student;
}
private:
int listOfStudents;
};
int main()
{
Students listOfStudents(ALI | REZA);
cout << "list of students : " << listOfStudents.showStudentsName() << endl;
cout << endl << "SAJJAD will be added to the list of students." << endl;
listOfStudents.add(SAJJAD);
cout << "list of students : " << listOfStudents.showStudentsName() << endl;
cout << endl << "REZA will be removed from the list of students." << endl;
listOfStudents.destroy(REZA);
cout << "list of students : " << listOfStudents.showStudentsName() << endl;
cout << endl << "Is REZA on the list of students?" << endl;
cout << (listOfStudents.isExist(REZA) ? "Yes, there is." : "No, it does not exist.") << endl;
return 0;
}