عملیات بیتی (Bit Manipulation)
عملیات بیتی: AND/OR/XOR و ترفندهای آن‌ها؛ تک‌بیتی گمشده، شمارش یک‌ها و مجموعه با بیت‌مپ
چرا بیت‌ها؟
کامپیوتر در سطح بیت کار می‌کند — عملیات بیتی سریع‌ترین عملیات‌ها هستند و برای مسائل خاص، راه‌حل‌های فوق‌العاده ظریف می‌سازند.
عملگرهای پایه
| عملگر | نام | مثال (۵=101، ۳=011) |
|---|---|---|
| & | AND | 101 & 011 = 001 |
| | | OR | 101 | 011 = 111 |
| ^ | XOR | 101 ^ 011 = 110 |
| ~ | NOT | ~101 = ...010 (معکوس) |
| << | شیفت چپ | 101 << 1 = 1010 (×۲) |
| >> | شیفت راست | 101 >> 1 = 10 (÷۲) |
خواص جادویی XOR
- x ^ x = 0 (خودش را خنثی می‌کند)
- x ^ 0 = x
- جابه‌جایی و شرکت‌پذیری
نتیجه: XOR همه اعداد جفت + یک تکی = همان تکی! (پایه «تک‌بیتی گمشده»)
ترفندهای پرکاربرد
| ترفند | کد | کاربرد |
|---|---|---|
| فرد/زوج | n & 1 | ۱ = فرد |
| توان ۲؟ | n & (n-1) == 0 | ۸=1000، ۷=0111 |
| حذف آخرین بیت ۱ | n & (n-1) | شمارش یک‌ها |
| آخرین بیت ۱ | n & (-n) | BIT/Fenwick |
| ضرب/تقسیم ۲ | n << 1 / n >> 1 | سریع |
| جابه‌جایی بدون متغیر | a ^= b; b ^= a; a ^= b | ترفند معروف |
مسائل کلاسیک
- تک‌عدد گمشده: XOR همه مورد انتظار و واقعی
- تک‌عدد در میان جفت‌ها: XOR همه — جفت‌ها صفر!
- شمارش بیت‌های ۱: حلقه با n & (n-1)
- مجموعه با بیت‌مپ: هر بیت = عضو؛ union=|، intersection=&، add=| (1<
- زیرمجموعه‌ها با بیت: از 0 تا 2ⁿ−1، هر عدد = یک ماسک زیرمجموعه!
نکته: در پایتون اعداد بی‌نهایت‌اند (بدون سرریز) اما در C++/Java با شیفت‌ها مراقب signed/unsigned باشید. برای ماسک‌های بزرگ، پایتون راحت‌ترین است!
جمع‌بندی
- XOR: خودخنثی — پایه مسائل جفت/تکی
- n & (n-1): حذف آخرین یک — شمارش و توان ۲
- بیت‌مپ: مجموعه فشرده و سریع
- ماسک 0 تا 2ⁿ−1 = همه زیرمجموعه‌ها
این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.