عملیات های بیتی

توضیحات

مبنای ۲ اعداد

در دنیای کامپیوتر، مبنای ۲ اعداد، مثل مبنای ۱۰ از اهمیت زیادی برخوردار هستند، به صورت کلی، در دنیای کامپیوتر هر چیزی به دنباله از ۰ و ۱ ها مدل می‌شوند. همچنین هر رقم در مبنای ۲ اعداد که میتواند مقدار ۰ یا ۱ داشته باشد بیت نامیده میشود.

به طور کلی، متغیر از جنس unsigned int در سی پلاس پلاس، از ۳۲ بیت تشکیل شده، برای همین یک متغیر از جنس unsigned int می‌تواند مقادیر ۰ تا \(2^{32} - 1\) را به خود بگیرد. این موضوع برای متغیر از جنس int کمی پیچیده تر است، چرا که می‌توان اعداد منفی را هم در int ذخیره کرد. نحوه‌ی نگهداری اعداد مثبت حدودا مشابه است اما اعداد منفی به شکل متفاوتی نگهداری می‌شوند. (در صورت علاقه، برای مطالعه بیشتر به این لینک مراجعه کنید).

همچنین برای تعریف یک متغیر از جنس ۰ یا ۱ در سی پلاس پلاس، میتوان از bool استفاده کرد.

عملیات های بیتی

برای ۲ بیت مانند \(a\) و \(b\) (که تنها مقادیر ۰ یا ۱ را به خود می‌گیرند) چند عملگر معروف(مانند ضرب و جمع برای اعداد صحیح) تعریف می‌شود:

• عملگر not: این عملگر یک بیت مانند \(a\) را گرفته، و برعکس آن را خروجی می‌دهد(اگر ۰ بود ۱ و در غیر این صورت ۰ را خروجی می‌دهد).
• عملگر and: این عملگر ۲ بیت \(a\) و \(b\) را گرفته و اگر هر دوی آنها برابر ۱ بودند، ۱ را خروجی می‌دهد(در غیر اینصورت حاصل عملگر and صفر است).
• عملگر or: این این عملگر ۲ بیت \(a\) و \(b\) را گرفته و اگر حداقل یکی از آنها برابر ۱ بود، ۱ را خروجی می‌دهد(در غیر اینصورت حاصل عملگر or صفر است).
• عملگر xor: این این عملگر ۲ بیت \(a\) و \(b\) را گرفته و اگر دقیقا یکی از آنها برابر ۱ بود، ۱ را خروجی می‌دهد(در غیر اینصورت حاصل عملگر xor صفر است).

این ۴ عملیات، در سی پلاس پلاس از قبل تعریف شده و قابل استفاده هستند:

bool a = true;
bool b = false;

bool c = !a; // not
bool d = a & b; // and
bool e = a | b; // or
bool f = a ^ b; // xor

همچنین به سادگی، میتوان این ۴ عملیات را روی ۲ متغیر از جنس int نیز تعریف کرد، برای مثال، اگر \(a\) و \(b\) تو متغیر از جنس int باشند، بیت \(i\)ام \(a \& b\) را برابر با and بیت \(i\)ام \(a\) و بیت \(i\)ام \(b\) قرار میدهیم، بدین صورت، حاصل and دو متغیر \(a\) و \(b\) نیز یک عدد ۳۲ بیتی خواهد بود.

برای همین، این ۴ عملیات با تعریف ذکر شده، در سی پلاس پلاس برای متغیر های عددی نیز تعریف شده اند(همچنین خروجی هر یک برای درک بهتر شما داده شده):

unsigned int a = 12, b = 5; // (1)!

unsigned int c = ~a; // (2)!
unsigned int d = a & b; // (3)!
unsigned int e = a | b; // (4)!
unsigned int f = a ^ b; // (5)!

1. a = 000...01100, b = 000...00101
2. not -> c = 111...10011
3. and -> d = 000...00100
4. or -> e = 000...01101
5. xor -> f = 000...01001

در سی پلاس پلاس، روی ۲ عدد \(a\) و \(k\) دو عملگر پرکاربرد دیگر نیز تعریف میشوند:

• شیفت چپ: \(k\) رقم ابتدایی(از سمت راست) در نمایش دودویی عدد \(a\) را حذف کرده و \(k\) رقم ۰ به انتهای \(a\) در نمایش دودویی اش اضافه میکند.
• شیفت راست: \(k\) رقم انتهایی در نمایش دودویی عدد \(a\) را حذف کرده و \(k\) رقم ۰ به ابتدای \(a\) در نمایش دودویی اش اضافه میکند.

int a = 9; // (1)!
int b = (a << 2); // (2)!
int c = (a >> 2); // (3)!

1. a = 000...001001
2. left shift, b = 000...00100100
3. right shift, c = 000...00010

گرفتن یک بیت دلخواه از یک عدد

از ترکیب ۶ عملیات پایه ای ذکر شده، میتوان عملیات های پیچیده تری ساخت، برای مثال میتوان به راحتی اثبات کرد که کد زیر، \(k\)امین بیت عدد \(n\) را به عنوان خروجی بر میگرداند.(همچنین از شبه کد زیر در ادامه استفاده زیادی شده، برای همین توصیه میشود به خوبی آن را درک کنید).

int n, k;
cin >> n >> k;
cout << ((n >> k) & 1) << endl;

نمایش زیرمجموعه های یک مجموعه

یکی از کاربرد مبنای ۲ اعداد در دنیای الگوریتم، نمایش زیرمجموعه های یک مجموعه است، به طور کلی، میتوان تناظری یک به یک بین تمام اعداد \(k\) بیتی و تمام زیرمجموعه های یک مجموعه \(k\) عضوی به صورت زیر برقرار کرد:

اگر عضو \(i\)ام مجموعه(از ۰ تا \(k - 1\)) در زیرمجموعه دلخواه حضور داشت، بیت \(i\)ام عدد ذکر شده را ۱ گذاشته و در غیر این صورت بیت متناظر را ۰ میگذاریم.

به طور عامیانه، به عدد نمایانگر یک زیرمجموعه از مجموعه \(k\) عضوی، مسک(mask) آن مجموعه گفته میشود.

حال با استفاده از تناظر ذکر شده، میتوان کدی زد که یک مجموعه \(n\) عضوی را از ورودی بگیرد و تمام زیرمجموعه های آن را چاپ کند.

برای این کار کافیست روی تمام مقادیر ۰ تا \(2^n\) فور زده و به ازای هر بیت ۱، عضو متناظر با آن بیت را در زیرمجموعه قرار دهیم.(\(O(2^n.n)\))

vector<int> vec;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    vec.push_back(x);
}

for (int mask = 0; mask < (1 << n); mask++) { // (2)!
    for (int b = 0; b < n; b++)
            if (((mask >> b) & 1)) // (1)!
                cout << vec[b] << ' ';
    cout << endl;
}

1. در این خط، به کمک عملگرهای گفته شده، چک میشود که آیا بیت \(b\) ام متغیر \(mask\) برابر ۱ است یا خیر.

2. دقت کنید میتوان گفت که مقدار \(1 << n\) برابر ۲ به توان \(n\) است.

تمرین

سعی کنید با گرفتن دو مسک متناظر با دو زیرمجموعه، در \(O(1)\) بفهمید آیا اولی زیرمجموعه دومی است یا خیر.

نمایش زیرمجموعه های هر زیرمجموعه

در برخی از سوالات، نیاز میشود به ازای هر زیرمجموعه، روی تمام زیرمجموعه های آن زیرمجموعه فور بزنیم.به صورت کلی، به تمام دوتایی مرتب های (\(B, C\)) به شکل \(C \subseteq B \subseteq A\) نیاز داریم.(میتوان ثابت کرد که تعداد این دوتایی مرتب ها، برابر \(3^n\) است)، یک راه ساده برای اینکار، این است که به ازای هر زیرمجموعه، تمام زیرمجموعه های آن را پیدا کنیم، اما کد ساده تری نیز برای اینکار وجود دارد

for (int mask_B = 0; mask_B < (1 << n); mask_B++) {
    for (int mask_C = mask_B; mask_C > 0; mask_C = (mask_C - 1) & mask_B) {
        // کد دلخواه
    }

    // (1)!
}

1. mask_C مقدار ۰ را به خودش نمیگیرد. این حالت را میتوان جداگانه چک کرد

اثبات درستی الگوریتم

میگوییم مسک mask_C ساب مسک mask_B است اگر و تنها اگر مجموعه متناظر با mask_C زیرمجموعه مجموعه متناظر با mask_B باشد. حال ثابت میکنیم در شبه کد فوق، mask_C تمامی سابمسک های mask_B را به ترتیب کتابخانه ای(لکسیکوگرافیکال) از بزرگ به کوچک طی میکند.(در مبنای ۲)

به راحتی میتوان دید مقدار اولیه mask_C بزرگترین سابمسک ممکن از لحاظ کتابخانه ای است.

فرض کنید آخرین بیت ۱ mask_C بیت \(i\)ام آن باشد. با کاهش ۱ واحد از mask_C، تمام بیت های جلو تر از بیت \(i\) برابر ۱ شده و بیت \(i\) برابر ۰ میشود.

در ادامه بیت های اضافه ای که برابر با ۱ شده اند(زیرمجموعه mask_B نیستند)، با عملیات bitwise and بین mask_C و mask_B برابر ۰ میشوند.

میتوان دید آخرین عضو mask_C پس از عملیات های فوق حذف شده و تمامی اعضای بعد آن که قبلا در mask_C نبوندن به mask_C اضافه شده اند که با کمی برسی، میتوان دید دقیقا به عضو بعدی در ترتیب کتابخانه ای رسیده ایم.

چند تابع کاربردی در GCC

• تعداد بیت های عدد \(x\) در نمایش دودویی:

  __builtin_popcount(x)

• تعداد بیت های ۰ بعد آخرین بیت ۱ عدد \(x\) در نمایش دودویی:

  __builtin_ctz(x)

• تعداد بیت های ۰ قبل اولین بیت ۱ عدد \(x\) در نمایش دودویی:

  __builtin_clz(x)

• کف لاگ در مبنای ۲ \(x\)(بدون خطای اعشاری):

  __lg(x)

توجه کنید که توابع گفته شده از \(O(1)\) زمان میبرند. زیرا عملیات‌های درونی هستند و مشابه عملیات های ضرب و جمع محاسبه میشوند. پس هر کدام یک عملیات به حساب می‌آید.

برای استفاده توابع فوق برای متغیر های از جنس long long، به انتهای آنها عبارت ll را اضافه کنید.

منابع بیشتر

• Bitwise operations for beginners
• Submask Enumeration

سوال ها

سوال	سختی	تگ ها	جاج
Fedor and new game	1100	Spoiler عملیات های بیتی	Codeforces
Petr and a Combination Lock	1200	Spoiler عملیات های بیتی	Codeforces
New Year's Eve	1300	Spoiler عملیات های بیتی	Codeforces
Preparing Olympiad	1400	Spoiler عملیات های بیتی	Codeforces
Xor Guessing	1700	Spoiler عملیات های بیتی	Codeforces
AND, OR and square sum	1700	Spoiler عملیات های بیتی	Codeforces
Apollo versus Pan	1800	Spoiler عملیات های بیتی	Codeforces
Bitwise Queries (Hard Version)	2300	Spoiler عملیات های بیتی	Codeforces
Anton and School	2500	Spoiler عملیات های بیتی	Codeforces

نظرات