این تکنیک برای مدیریت و عضو کردن یکسری عناصر به مجموعه است. مجموعه در اینجا با عنوان رشته بیتی یاد میشود که هر بیت آن نشان دهندهی وضعیتِ عنصر مورد نظر میباشد. اگر عنصر مورد نظر در مجموعه یا رشته بیتی عضو است، آنگاه بیت متناظر آن در رشته بیتی، شامل مقدار یک است، در غیر این صورت، این بیت صفر خواهد بود.
نکته: باید برای هر عنصر مجموعه، maskای را در نظر گرفته شود.
تا اینجا دو مولفه، به نامهای رشته بیتی که همان مجموعه است و mask که مربوط به هر عنصر مجموعه است اشاره شد.
در زیر چندین عملیات بیان میشود که میتوان روی مجموعه یا رشته بیتی انجام داد؛ این عملیاتها با کمک عملگرهای بیتی انجام میپذیرد:
منظور این هست که بررسی شود بیت متناظر با عنصر، دارای مقدار یک هست یا صفر؛ اگر مقدار صفر هست یعنی عنصر عضو مجموعه نیست و اگر بیت مربوطه مقدار یک است، یعنی عنصر عضو مجموعه است(با استفاده از عملگر منطقی &).
این عملیات به صورت زیر انجام میپذیرد:
(رشته بیتی) & (عنصر مورد نظر)
نکته: منظور از عنصر مورد نظر، مقدار mask آن میباشد.
منظور این هست که بیت متناظر با عنصر، در مجموعه یا رشته بیتی، دارای مقدار یک گردد(با استفاده از عملگر منطقی or).
(رشته بیتی) | (عنصر مورد نظر)
منظور این هست که بیت متناظر با عنصر، در مجموعه یا رشته بیتی، دارای مقدار صفر گردد(با استفاده از عملگر منطقی or و not).
(رشته بیتی) | (عنصر مورد نظر~)
نکته: علامت not یا معکوس به صورت ~ میباشد.
منظور این است که اگر مقدار بیت متناظر با عنصر در رشته بیتی، دارای مقدار یک بود، صفر گردد یعنی عنصر، از مجموعه حذف گردد و همچنین اگر مقدار بیت متناظر با عنصر، در رشته بیتی، صفر بود دارای مقدار یک گردد، یعنی عنصر به مجموعه اضافه شود. در اصطلاح به این نوع عملیات تغییر وضعیت، toggle گفته می شود (با استفاده از عملگر منطقی xor).
(رشته بیتی) ^ (عنصر مورد نظر)
لیستی از افراد به صورت زیر وجود دارد:
List of persons = ALI, HASAN, REZA, SAJJAD.
در این لیست، فقط ALI، REZA و SAJJAD دانشجو هستند؛ میخواهیم مجموعهای از دانشجویان را ایجاد نماییم و عملیاتهایی مانند بررسی عضو بودن دانشجو در مجموعه، حذف دانشجو از مجموعه، عضو کردن دانشجوی جدید به مجموعه را، انجام دهیم:
در ابتدا لازم هست که مجموعه یا همان رشته بیتی که شامل دانشجویان هست را ایجاد نماییم:
int listOfStudents = 0;
در ادامه برای هر عنصر (افراد)، لازم است maskی ایجاد شود:
const int ALI {0b1000};
const int HASAN {0b0100};
const int REZA {0b0010};
const int SAJJAD {0b0001};
نکته: به طور کلی تعداد افراد با تعداد بیتها، یکسان است و دلیل این امر به خاطر متمایز کردن افراد نسبت به یکدیگر میباشد (میتوان به این صورت بیان کرد: به هر فرد یک ID یا شناسه منحصر به فرد، داده شده است).
نکته: مقدار 0b0001، عدد باینری (دودیی) را نشان میدهد.
listOfStudents = listOfStudents | ALI;
listOfStudents = listOfStudents | REZA;
listOfStudents = listOfStudents | SAJJAD;
اکنون مقدار listOfStudents ، عدد 11 میباشد که به صورت دودویی یا باینری عدد 1011 است که نشاندهندهی عضو بودن سه دانشجو ALI، REZA و SAJJAD در مجموعه است (یعنی بیتهای متناظر این افراد، یک میباشند).
سه خط کد بالا را می توان به صورت زیر خلاصه کرد:
listOfStudents = listOfStudents | (ALI | REZA | SAJJAD);
listOfStudents = listOfStudents & (~REZA)
اکنون مقدارlistOfStudents ، عدد 9 است که به صورت دودویی 1001 میباشد و نشان میدهد که کاربر REZA از مجموعه حذف گردیده است.
سوال) برای حذف کردن دو دانشجو، چه کدی باید نوشت؟
جواب) به عنوان نمونه برای حذف دانشجوهای ALI و REZA به صورت زیر باید اقدام کرد:
listOfStudents = listOfStudents & (~(ALI | REZA))
isExist = listOfStudents & REZA
چون در عملیات قبلی دانشجوی REZA را حذف نمودیم، مقدار isExist، صفر میباشد.
isExist = listOfStudents & SAJJAD
مقدار isExist، یک میباشد و نشان از عضو بودن SAJJAD در مجموعه دانشجویان است.
نکته: در کتابخانههای استاندارد ++C ، کتابخانهای با نام bitset برای تسهیل مدیریت و کار با تکنیک mask، وجود دارد.
#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;
}