مقدماتی :
یکی از مباحثی که همیشه به عنوان حاشیه در کلاس های آموزشی برنامه نویسی آموزش داده میشود عملیات بیتیست (bitwise operation ) که به نظر من یکی از مهم ترین مفاهیمی است که می تواند یک برنامه نویس حرفه ای را از یک برنامه نویس معمولی متمایز سازد.
خلاصه ای از این عملگرها را در زیر می بینید :
01001000 & 01001000 | 01110010 ^ 10111000 = 10111000 = 10101010 01110010 ! -------- -------- -------- -------- 00001000 11111000 11011000 10001101
01110010 >> 01110010 <<-------- --------00111001 11100100
متوسط :
چند هم ارز با استفاده از عملگر های بیتی:
- x % 2 : x&1
- pow( 2 , k ) : 1<<k
- x % pow(2 , k ) : x & ( (1<<k) - 1 )
- x* 2k : x<<k
- x / 2k : x>>k
در بعضی از سوالات می توان با استفاده از این عملگرها فرایند مارک کردن یا به طور کلی فرایندهایی که شامل ۲ حالت ۰ و ۱ با وسعتی کمتر از۳۱ میباشد را بهینه کرد. برای این کار نیاز است که به تک تک بیت های متغیر دسترسی داشته باشیم و عملیات دلخواه را روی بیت انجام دهیم که در زیر به سه تا از مهمترین آنها اشاره کردم.
To “set” a bit : a |= (1 << n); قرار دادن ۱
To “clear” a bit: b &= ~(1 << n); قرار دادن ۰
To “toggle” a bit: c ^= (1 << n); جایگزین کردن یک با صفر ـ یا بالعکس
پیشرفته:
ماسک کردن:
فرض کنید که می خواهیم باقیمانده ی یک عدد بزرگ (برای مثال ۱۲۳۴۵۶۷۸۹۰۱۲۳۴۵۶۷۸۹۰۱۲۳۴۵۶۷۸۹۰) به ۱۰۰۰۰۰ را بدست آوریم. چیزی که اینجا مشهود است نیازما تنها به چند رقم سمت راست است. پس می توانیم برای overflow نکردن همواره چند رقم اول را نگه داریم. این عمل را من ماسک کردن می نامم.
هدف از تعریف کردن ماسک این است که در بعضی از سوالات تقریبا Big number که در ادامه ی سورس متغیر با عملیات بیتی سر و کار دارد ابتدا می توانیم ماسک را بدین صورت تعریف کنیم.
#define MASK 0xFF. . .FFFF (به مقدار لازم )
این عبارت برابر عدد ۱ . . .۱۱۱۱ می باشد.
سپس در طول برنامه (جاهایی که با افزایش متغیر همراه هستیم) از عبارت زیر استفاده می کنیم :
x &= MASK;
این عمل از overflow شدن متغیر جلوگیری می کند.
