آرایه بیتی

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

تعریف

آرایه بیتی یک نگاشت از (معمولاً) اعداد صحیح به مجموعه {0,1} است. به این دلیل که فقط دو مقدار وجود دارند می‌توان هر کدام را در یک بیت نگهداری کرد.

عملیات های ساده

اگر چه اکثر ماشین ها قابلیت آدرس دهی بیت های مجزا در حافظه را ندارند و دستورهای ماشین نمی توانند مستقیما بیت ها را تغییر دهند، اما می توان به کمک عملیات های بیتی AND, OR, XOR این عملیات ها را پیاده سازی کرد:

• برای قرار دادن یک درون یک بیت، می توان از عملگر OR استفاده کرد:

11101010 OR 00000100 = 11101110

• برای قرار دادن صفر درون یک بیت، می توان از عملگر AND استفاده کرد:

11101010 AND 11111101 = 11101000

• با عملگر AND و چک کردن این که یک کلمه ۰ است یا نه، می توان مقدار یک بیت را به دست آورد:

11101010 AND 00000001 = 00000000 = 0
11101010 AND 00000010 = 00000010 ≠ 0

• با عملگر XOR می توان مقدار یک بیت را برعکس کرد:

11101010 XOR 00000100 = 11101110
11101110 XOR 00000100 = 11101010

همچنین عملیات های اجتماع، اشتراک و مکمل در مجموعه ها را به ترتیب می توان با عملیات های OR ، AND ، NOT انجام داد. برای هر کدام از این عمل های مجموعه ای، n/w تا عملیات بیتی نیاز است.

عملیات های پیچیده تر

مانند رشته های کاراکتری می توان عملیات های طول، زیر رشته، مقایسه لکسیکوگرافی یا چسباندن را تعریف کرد. بعضی از این عملیات ها به اندیان حساس هستند.

تعداد یک ها

برای به دست آوردن تعداد یک های یک آرایه بیتی، که به آن جمعیت یا وزن همینگ نیز گفته می شود، می توان تعداد یک ها را برای هر کلمه به طور جداگانه به دست آورد. برای مشاهده پیاده سازی بهینه، مقاله وزن همینگ را ببینید.

معکوس کردن

بعضی از الگوریتم ها مانند الگوریتم های تبدیل سریع فوریه، به معکوس کردن یک آرایه بیتی نیاز دارند. در پردازنده هایی که از این عملیات پشتیبانی می کنند، می توان این کار را با n/w عملیات انجام داد.

پیدا کردن اولین یک

پیدا کردن اولین یک نیز یکی از قابلیت هایی است که در یک کلمه از پشتیبانی سخت افزاری گسترده ای برخوردار است. این عملیات در پیاده سازی صف اولویت به کمک آرایه بیتی کاربرد دارد.

کاربرد

یکی از کاربردهای آرایه بیتی در فیلتر بولوم می‌باشد که نوعی داده ساختار احتمالاتی با قابلیت ذخیره‌سازی مجموعه‌های بزرگ در فضای کوچک در ازای خطای اندک می‌باشد.

آرایه‌های بیتی همچنین در صف‌های اولویت و ساخت جداول درهم سازی و بررسی جریان فشرده‌سازی داده‌ها به کار می‌رود.

جستارهای وابسته

• دستگاه اعداد دودویی
• عملیات بیتی

منابع

ویکی‌پدیا انگلیسی