Bits and Bitmask

Эхлээд битийн үйлдлүүдийн талаар товчхоон тайлбарлая. Хоёртын үйлдлүүд болох (& and), (| or), (~ not), (^ xor) нь дараахь үнэний хүснэгтэд тулгуурлаж хариуг гаргадаг.

Өгөгдсөн тоонуудын хувьд хоёртын үйлдэл хийнэ гэдэг маань тухайн тоонуудын хоёртын бичиглэл дахь ижил байранд байгаа бит (0, 1) болгонд үйлдэл хийж шинэ битийг гаргахыг хэлэх юм. Жишээ нь A=10, B=12 гэсэн хоёр тоонд битийн үйлдлүүд хийж үзье. Энэ тохиолдолд А тооны хоёртын бичиглэл = 1010, B тооны хоёртын бичиглэл=1100 юм.

• A & B = 1000 = 8
  
• A | B = 1110 = 13
  
• A ^ B = 0110 = 5

Өөр нэг чухал үйлдэл бол бит шилжүүлэлт <<, >> юм. a << b энэ үйлдэл нь a-н хоёртын бичиглэл дахь бүх битүүдийг зүүн тийш b удаа шилжүүлэх юм. a>>b гэвэл эсрэгээрээ a-н бүх битүүдийг баруун тийш b удаа шилжүүлэх юм. Шилжүүлсний дараах хуучин оронг 0 болгоно. Жишээ нь: 3<<1 гэвэл хариу 6 болно( 3 = 11_2, 3<<1 = 110₂ = 6). Хэрэв бит шилжүүлэлтийн үйлдэлийг сайн ажиглах юм бол a << b энэ нь a-г 2^b-ээр үржүүлсэнтэй тэнцүү a >> b нь a-г 2^b-д хуваасантай тэнцүү. Энэ үйлдэлийг ихэвчлэн өгөгдсөн тооны тодорхой байрлалд байгаа бит-д хандахад хэрэглэдэг юм. Жишээ нь С тооны хоёртын бичиглэлийн b-р бит нь 1 мөнүү гэдэгийг шалгая гэвэл if( C&(1 << b) ) [битийг дугаарлахдаа зүүн талаас нь дугаарладаг!].
За одоо bitmask-н талаар тайлбарлая.
Бидэнд өгөгдсөн олонлогийн бүх дэд олонлогийг байгуул гэсэн бодлого өгөдсөн байг. N элементтэй олонлогийн бүх дэд олонлог 2^N ширхэг байдаг. Тэгвэл яаж дэд олонлогуудаа байгуулах вэ? Тайлбарлахын тулд бодлогоо илүү энгийн болгоё.
Танд алим, жүрж, киви гэсэн гурван жимс байг. Тэгвэл жимснүүдээ хэдэн янзаар сонгож авч болох вэ?
Бодолт:
Жимс бүрийг нэг бит тоо гэж үзээд дэд олонлогоо үүсгэхдээ тухайн жимсийг сонгосон бол 1, сонгоогүй бол 0-ээр тэмдэглэе. Жишээ нь эхний удаад
ямар ч жимс сонгохгүй байвал 000,
зөвхөн киви сонговол 001,
зөвхөн жүрж сонговол 010,
зөвхөн алим сонговол 100,
алим киви сонговол 101, ийм сонголт нийтдээ 2^3 ширхэг байгаа. Хэрэв сайн ажиглавал 0 - 2³-1 тоо бүр нэг сонголтыг(дэд олонлогийг) илэрхийлж байна.
0 - 000
1 - 001
2 - 010
3 - 011
4 - 100
5 - 101
6 - 110
7 - 111
Дээрх тайлбараас бодолт тодорхой болсон байх гэж бодож байна.

За тэгээд bitmask гэж ерөнхийдөө дээрх аргыг хэлнэ. Bitmask-н хувьд хугацааны үнэлгээ O(2^N) болохоор үнэхээр битмаск мөнүү бишүү гэдэгийг сайн бодож бодоорой.