پرش به محتویات

کار با بیت‌ها

عدد دودویی (Binary)

خب رفیق، بیا با هم یه نگاهی به دنیای صفر و یک‌ها بندازیم. عدد دودویی یا همون باینری، عددیه که توی سیستم عددی مبنای ۲ نشون داده میشه. خیلی ساده، یه روش برای نشون دادن عددهاست که فقط با دوتا نماد کار می‌کنه: معمولاً «۰» (صفر) و «۱» (یک).

وقتی یه بیت مقدارش ۱ باشه، بهش میگیم روشن (set)، و اگه صفر باشه، میگیم خاموش (unset).

یه عدد باینری مثل $(a_k a_{k-1} \dots a_1 a_0)_2$ در واقع این عدد رو نشون میده:

$$(a_k a_{k-1} \dots a_1 a_0)_2 = a_k \cdot 2^k + a_{k-1} \cdot 2^{k-1} + \dots + a_1 \cdot 2^1 + a_0 \cdot 2^0.$$

مثلاً، عدد باینری $1101_2$ همون عدد $13$ خودمون هست:

$$\begin{align} 1101_2 &= 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 \\ &= 1\cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1 \cdot 1 = 13 \end{align}$$

کامپیوترها هم دقیقاً اعداد صحیح رو به همین شکل باینری ذخیره و پردازش می‌کنن. عددهای صحیح مثبت (چه علامت‌دار و چه بدون علامت) خیلی راحت با همین ارقام باینری‌شون نشون داده میشن، و عددهای صحیح علامت‌دار منفی (یعنی اونایی که می‌تونن مثبت یا منفی باشن) معمولاً با یه روشی به اسم Two's complement نشون داده میشن.

unsigned int unsigned_number = 13;
assert(unsigned_number == 0b1101);

int positive_signed_number = 13;
assert(positive_signed_number == 0b1101);

int negative_signed_number = -13;
assert(negative_signed_number == 0b1111'1111'1111'1111'1111'1111'1111'0011);

پردازنده‌ها (CPU) خدای دستکاری این بیت‌ها هستن و این کارها رو با یه سری عملیات خاص، برق‌آسا انجام میدن. برای همین، توی بعضی مسئله‌ها می‌تونیم از این نمایش باینری به نفع خودمون استفاده کنیم و سرعت اجرای برنامه رو ببریم بالا. یه کاربرد باحال دیگه‌ش (مخصوصاً تو مسائل ترکیبیات یا برنامه‌نویسی پویا) اینه که وقتی می‌خوایم حواسمون باشه چه چیزهایی رو از یه مجموعه انتخاب کردیم، می‌تونیم از یه عدد صحیح بزرگ استفاده کنیم. هر بیت این عدد نماینده‌ی یه شیء از اون مجموعه‌ست. اگه شیء رو انتخاب کنیم، بیتش رو روشن می‌کنیم و اگه نه، خاموشش می‌کنیم. به همین سادگی!

عملگرهای بیتی (Bitwise Operators)

تمام عملگرهایی که اینجا معرفی می‌کنیم برای عددهای صحیح با طول ثابت، توی CPU تقریباً آنی اجرا میشن (سرعتشون در حد یه عمل جمع سادست).

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

  • & : عملگر AND بیتی. این عملگر میاد بیت به بیت دوتا عدد رو با هم مقایسه می‌کنه. اگه هر دوتا بیت ۱ باشن، بیت متناظر توی نتیجه هم ۱ میشه. در غیر این صورت، ۰ میشه.

  • | : عملگر OR بیتی. اینم بیت به بیت مقایسه می‌کنه. اگه حداقل یکی از دوتا بیت ۱ باشه، بیت نتیجه ۱ میشه. در غیر این صورت، ۰ میشه.

  • ^ : عملگر XOR بیتی (OR انحصاری). این یکی هم بیت به بیت کار می‌کنه. اگه بیت‌ها با هم فرق داشته باشن (یکی ۰ و اون یکی ۱)، بیت نتیجه ۱ میشه. اگه مثل هم باشن، ۰ میشه.

  • ~ : عملگر NOT بیتی (مکمل). این عملگر هر بیت یه عدد رو برعکس می‌کنه. اگه بیت روشن باشه، خاموشش می‌کنه و اگه خاموش باشه، روشنش می‌کنه.

بیا چندتا مثال ببینیم:

n         = 01011000
n-1       = 01010111
--------------------
n & (n-1) = 01010000

n         = 01011000
n-1       = 01010111
--------------------
n | (n-1) = 01011111

n         = 01011000
n-1       = 01010111
--------------------
n ^ (n-1) = 00001111

n         = 01011000
--------------------
~n        = 10100111

عملگرهای شیفت (Shift Operators)

دوتا عملگر هم داریم برای هُل دادن بیت‌ها به چپ و راست.

  • >> (شیفت به راست): این عملگر بیت‌های یه عدد رو به سمت راست هُل میده و بیت‌های آخر رو حذف می‌کنه. هر بار که یه بیت به راست شیفت میدی، انگار داری عدد رو تقسیم صحیح بر ۲ می‌کنی. پس اگه $k$ بار شیفت بدی، انگار عدد رو بر $2^k$ تقسیم کردی.

    مثلاً $5 \gg 2 = 101_2 \gg 2 = 1_2 = 1$ که دقیقاً مثل $\frac{5}{2^2} = \frac{5}{4} = 1$ هست. ولی خب برای کامپیوتر، شیفت دادن چندتا بیت خیلی سریع‌تر از یه عمل تقسیمه.

  • << (شیفت به چپ): این عملگر بیت‌ها رو به چپ هُل میده و سمت راستش صفر اضافه می‌کنه. اینم مثل شیفت به راسته، هر شیفت به چپ به اندازه $k$، معادل ضرب کردن عدد در $2^k$ هست.

    مثلاً $5 \ll 3 = 101_2 \ll 3 = 101000_2 = 40$ که دقیقاً مثل $5 \cdot 2^3 = 5 \cdot 8 = 40$ هست.

    یادت باشه که برای عددهای صحیح با طول ثابت، شیفت دادن زیاد به چپ باعث میشه بیت‌های باارزش (سمت چپی‌ها) از دست برن و اگه خیلی شیفت بدی، ممکنه به عدد $0$ برسی.

ترفندهای باحال

روشن کردن/برعکس کردن/خاموش کردن یه بیت

با استفاده از شیفت‌های بیتی و چندتا عملگر ساده، خیلی راحت می‌تونیم یه بیت خاص رو دستکاری کنیم. 1 << x یه عدد میسازه که فقط بیت $x$-اُمش روشنه. برعکسش، ~(1 << x) یه عدد میسازه که همه بیت‌هاش روشنن به جز بیت $x$-اُم.

  • n | (1 << x): بیت $x$-اُم عدد $n$ رو روشن می‌کنه.
  • n ^ (1 << x): بیت $x$-اُم عدد $n$ رو برعکس (flip) می‌کنه.
  • n & ~(1 << x): بیت $x$-اُم عدد $n$ رو خاموش می‌کنه.

چک کردن روشن بودن یه بیت

برای اینکه بفهمیم بیت $x$-اُم یه عدد روشنه یا نه، می‌تونیم عدد رو $x$ بار به راست شیفت بدیم تا بیت مورد نظرمون بیاد سر جای اول (بیت یکان). بعدش کافیه با ۱ AND کنیم تا فقط همون بیت بمونه.

bool is_set(unsigned int number, int x) {
    return (number >> x) & 1;
}

چک کردن بخش‌پذیری بر توانی از ۲

با عملگر &، می‌تونیم چک کنیم یه عدد $n$ زوجه یا فرد. اگه $n$ زوج باشه n & 1 == 0 و اگه فرد باشه n & 1 == 1. حالا یه حالت کلی‌تر: $n$ بر $2^{k}$ بخش‌پذیره، اگر و فقط اگر n & (2^k - 1) == 0 باشه.

bool isDivisibleByPowerOf2(int n, int k) {
    int powerOf2 = 1 << k;
    return (n & (powerOf2 - 1)) == 0;
}

مقدار $2^{k}$ رو هم که با 1 << k حساب می‌کنیم. این ترفند کار می‌کنه چون $2^k - 1$ عددیه که دقیقاً از $k$ تا بیت ۱ پشت سر هم تشکیل شده. و عددی که بر $2^k$ بخش‌پذیره، باید $k$ بیت آخرش صفر باشه. پس AND این دوتا حتماً صفر میشه.

چک کردن اینکه یه عدد توانی از ۲ هست یا نه

یه عدد که توان ۲ باشه، فقط یه بیت ۱ داره (مثلاً $32 = 0010~0000_2$). حالا اگه یکی ازش کم کنی، اون بیت ۱ صفر میشه و تمام بیت‌های سمت راستش ۱ میشن ($31 = 0001~1111_2$). برای همین وقتی این دوتا رو با هم AND کنی (n & (n-1)), هیچ بیت مشترک روشنی ندارن و نتیجه میشه صفر. اگه یه کم فکر کنی، می‌بینی که این حالت فقط برای توان‌های ۲ و خود عدد $0$ اتفاق میفته.

bool isPowerOfTwo(unsigned int n) {
    return n && !(n & (n - 1));
}

خاموش کردن راست‌ترین بیت روشن

عبارت n & (n-1) راست‌ترین بیت روشن عدد $n$ رو خاموش می‌کنه. چرا؟ چون وقتی از $n$ یکی کم می‌کنی (n-1)، راست‌ترین بیت روشن و تمام بیت‌های بعد از اون برعکس میشن. در نتیجه، وقتی با $n$ اصلی AND می‌کنی، تمام اون بیت‌ها صفر میشن و فقط بیت‌های سمت چپ‌تر دست‌نخورده باقی می‌مونن.

مثلاً عدد $52 = 0011~0100_2$ رو ببین:

n         = 00110100
n-1       = 00110011
--------------------
n & (n-1) = 00110000

الگوریتم Brian Kernighan

با ترفند بالا می‌تونیم تعداد بیت‌های روشن یه عدد رو بشماریم.

ایده‌ش اینه که به جای اینکه بیت به بیت جلو بریم، فقط سراغ بیت‌های روشن میریم. توی هر مرحله، راست‌ترین بیت روشن رو با n & (n-1) خاموش می‌کنیم و یه دونه به شمارنده‌مون اضافه می‌کنیم. این کار رو اونقدر تکرار می‌کنیم تا عدد صفر بشه.

int countSetBits(int n)
{
    int count = 0;
    while (n)
    {
        n = n & (n - 1);
        count++;
    }
    return count;
}

شمردن بیت‌های روشن تا عدد $n$

اگه بخوایم تعداد کل بیت‌های روشن همه اعداد از ۱ تا $n$ رو حساب کنیم، می‌تونیم الگوریتم Brian Kernighan رو روی همه این اعداد اجرا کنیم. ولی این کار توی مسابقات احتمالاً "Time Limit Exceeded" میده.

یه راه بهتر اینه که از این نکته استفاده کنیم: برای اعداد تا $2^x$ (یعنی از $1$ تا $2^x - 1$)، تعداد کل بیت‌های روشن $x \cdot 2^{x-1}$ تاست. برای اینکه حسش کنی، به این الگو نگاه کن: 

0 ->   0 0 0 0
1 ->   0 0 0 1
2 ->   0 0 1 0
3 ->   0 0 1 1
4 ->   0 1 0 0
5 ->   0 1 0 1
6 ->   0 1 1 0
7 ->   0 1 1 1
8 ->   1 0 0 0

همونطور که می‌بینی، هر ستون (به جز چپ‌ترین) نصفش یکه. مثلاً برای اعداد تا $2^3 - 1 = 7$، هر کدوم از ۳ ستون سمت راست، $2^{3-1} = 4$ تا یک دارن. پس کل یک‌ها میشه $3 \cdot 2^{3-1}$.

با این دانش جدید، می‌تونیم این الگوریتم رو بسازیم:

  • بزرگترین توان ۲ که از $n$ کوچکتر یا مساویه رو پیدا کن. فرض کنیم توانش $x$ باشه.
  • تعداد بیت‌های روشن از $1$ تا $2^x - 1$ رو با فرمول $x \cdot 2^{x-1}$ حساب کن.
  • حالا تعداد بیت‌های روشن مربوط به پرارزش‌ترین بیت (بیت $x$-اُم) رو برای اعداد از $2^x$ تا $n$ حساب کن و اضافه کن. این تعداد میشه n - 2^x + 1.
  • $2^x$ رو از $n$ کم کن و همین مراحل رو برای $n$ جدید تکرار کن.
int countSetBits(int n) {
        int count = 0;
        while (n > 0) {
            int x = std::bit_width(n) - 1;
            count += x * (1 << (x - 1));
            n -= 1 << x;
            count += n + 1;
        }
        return count;
}

چندتا ترفند دیگه

  • n & (n + 1): تمام یک‌های آخر عدد رو خاموش می‌کنه: $0011~0111_2 \rightarrow 0011~0000_2$.
  • n | (n + 1): آخرین بیت خاموش رو روشن می‌کنه: $0011~0101_2 \rightarrow 0011~0111_2$.
  • n & -n: فقط آخرین بیت روشن رو نگه میداره و بقیه رو صفر می‌کنه: $0011~0100_2 \rightarrow 0000~0100_2$.

اگه دنبال ترفندهای خفن‌تر هستی، کتاب Hacker's Delight رو حتماً یه نگاهی بنداز.

پشتیبانی زبان و کامپایلر

خبر خوب اینه که لازم نیست همیشه این چرخ‌ها رو از اول اختراع کنی! C++ از نسخه C++20 به بعد، توی کتابخونه استاندارد bit یه سری از این کارها رو برات انجام میده:

  • has_single_bit: چک می‌کنه که عدد توانی از دو هست یا نه.
  • bit_ceil / bit_floor: عدد رو به نزدیک‌ترین توان دوی بعدی/قبلی گرد می‌کنه.
  • rotl / rotr: بیت‌های عدد رو می‌چرخونه (rotate).
  • countl_zero / countr_zero / countl_one / countr_one: تعداد صفرهای/یک‌های اول/آخر عدد رو می‌شماره.
  • popcount: تعداد بیت‌های روشن رو می‌شماره (همون الگوریتم Brian Kernighan خودمون، ولی بهینه!).

علاوه بر اینا، بعضی کامپایلرها مثل GCC یه سری تابع داخلی (built-in) دارن که حتی توی نسخه‌های قدیمی‌تر C++ هم کار می‌کنن:

  • __builtin_popcount(unsigned int): تعداد بیت‌های روشن رو برمی‌گردونه (__builtin_popcount(0b0001'0010'1100) == 4).
  • __builtin_ffs(int): ایندکس اولین (راست‌ترین) بیت روشن رو پیدا می‌کنه (__builtin_ffs(0b0001'0010'1100) == 3).
  • __builtin_clz(unsigned int): تعداد صفرهای اول عدد (leading zeros) رو برمی‌گردونه (__builtin_clz(0b0001'0010'1100) == 23 برای یه عدد ۳۲ بیتی).
  • __builtin_ctz(unsigned int): تعداد صفرهای آخر عدد (trailing zeros) رو برمی‌گردونه (__builtin_ctz(0b0001'0010'1100) == 2).
  • __builtin_parity(x): زوج یا فرد بودن تعداد یک‌ها رو برمی‌گردونه.

فقط حواست باشه که بعضی از این توابع (چه مال C++20 و چه توابع داخلی کامپایلر) ممکنه توی GCC کند باشن، مگه اینکه با #pragma GCC target("popcnt") بهش بگی که از دستورات سخت‌افزاری خاص استفاده کنه.

مسائل تمرینی

برای اینکه دستت راه بیفته، این چندتا مسئله رو حل کن: