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

دستکاری بیت‌ها

عدد دودویی

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

می‌گوییم یک بیت خاص روشن است اگر مقدار آن یک باشد، و خاموش است اگر مقدار آن صفر باشد.

عدد دودویی $(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) در دستکاری این بیت‌ها با عملیات خاص بسیار سریع هستند. برای برخی مسائل می‌توانیم از این نمایش اعداد دودویی به نفع خود استفاده کرده و زمان اجرا را سرعت ببخشیم. و برای برخی مسائل (معمولاً در ترکیبیات یا برنامه‌نویسی پویا) که می‌خواهیم اشیایی را که از یک مجموعه معین انتخاب کرده‌ایم ردیابی کنیم، می‌توانیم از یک عدد صحیح به اندازه کافی بزرگ استفاده کنیم که در آن هر بیت نماینده یک شیء باشد و بسته به اینکه شیء را انتخاب یا رها می‌کنیم، آن بیت را روشن یا خاموش کنیم.

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

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

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

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

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

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

  • ~ : عملگر مکمل (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

عملگرهای شیفت

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

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

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

  • << یک عدد را به چپ شیفت می‌دهد و در سمت راست آن صفرهایی اضافه می‌کند. مشابه شیفت به راست به اندازه $k$، یک شیفت به چپ به اندازه $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$ را معکوس می‌کند.
  • n & ~(1 << x) بیت $x$-ام عدد $n$ را خاموش می‌کند.

بررسی روشن بودن یک بیت

مقدار بیت $x$-ام را می‌توان با شیفت دادن عدد به اندازه $x$ موقعیت به راست بررسی کرد، به طوری که بیت $x$-ام در جایگاه یکان قرار گیرد، و پس از آن می‌توانیم با انجام یک AND بیتی با ۱، آن را استخراج کنیم.

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

بررسی بخش‌پذیری عدد بر توانی از ۲

با استفاده از عملگر and، می‌توانیم بررسی کنیم که آیا عدد $n$ زوج است یا نه، زیرا اگر $n$ زوج باشد n & 1 == 0 و اگر $n$ فرد باشد 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}$ را با شیفت دادن ۱ به چپ به تعداد $k$ موقعیت محاسبه کنیم. این ترفند کار می‌کند، زیرا $2^k - 1$ عددی است که دقیقاً از $k$ عدد یک تشکیل شده است. و عددی که بر $2^k$ بخش‌پذیر باشد باید در آن موقعیت‌ها ارقام صفر داشته باشد.

بررسی اینکه آیا یک عدد صحیح توانی از ۲ است

یک توان از دو عددی است که تنها یک بیت روشن دارد (مثلاً $32 = 0010~0000_2$)، در حالی که عدد قبلی آن این بیت را روشن ندارد و تمام بیت‌های بعد از آن روشن هستند ($31 = 0001~1111_2$). بنابراین AND بیتی یک عدد با عدد قبلی‌اش همیشه ۰ خواهد بود، زیرا هیچ بیت روشن مشترکی ندارند. می‌توانید به راحتی بررسی کنید که این حالت فقط برای توان‌های دو و برای عدد $0$ که از قبل هیچ بیت روشنی ندارد، اتفاق می‌افتد.

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

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

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

برای مثال، عدد $52 = 0011~0100_2$ را در نظر بگیرید:

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

الگوریتم Brian Kernighan

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

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

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

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

برای شمارش تعداد بیت‌های روشن همه اعداد تا عدد $n$ (شامل خود $n$)، می‌توانیم الگوریتم Brian Kernighan را بر روی تمام اعداد تا $n$ اجرا کنیم. اما این کار در مسابقات منجر به خطای "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

می‌توانیم ببینیم که تمام ستون‌ها به جز چپ‌ترین ستون، هر کدام $4$ (یعنی $2^2$) بیت روشن دارند، یعنی تا عدد $2^3 - 1$، تعداد بیت‌های روشن برابر $3 \cdot 2^{3-1}$ است.

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

  • بزرگترین توان ۲ را که کوچکتر یا مساوی عدد داده شده است، پیدا کنید. فرض کنید توان آن $x$ باشد.
  • تعداد بیت‌های روشن از $1$ تا $2^x - 1$ را با استفاده از فرمول $x \cdot 2^{x-1}$ محاسبه کنید.
  • تعداد بیت‌های روشن در پرارزش‌ترین بیت از $2^x$ تا $n$ را بشمارید و آن را اضافه کنید.
  • $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: بیت‌های عدد را می‌چرخاند.
  • countl_zero / countr_zero / countl_one / countr_one: تعداد صفرهای/یک‌های پیشرو/پسرو را می‌شمارد.
  • popcount: تعداد بیت‌های روشن را می‌شمارد.

علاوه بر این، توابع از پیش تعریف شده‌ای نیز در برخی کامپایلرها وجود دارند که به کار با بیت‌ها کمک می‌کنند. مثلاً، GCC لیستی را در Built-in Functions Provided by GCC تعریف کرده است که در نسخه‌های قدیمی‌تر C++ نیز کار می‌کنند:

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

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

مسائل تمرینی