آرایه بیتی

آرایه بیتی یک نگاشت از (معمولاً) اعداد صحیح به مجموعه {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 عملیات انجام داد.

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

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

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

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

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

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