Bitmask provide an efficient way to manipulate a small set of Booleans that is stored as a 32-(or 64-)bit signed integer in base-10 but interpreted as a short 32-(or 64-) characters string.
By using bitwise operations, each bit of the integer can be checked, turned on (or turned off) easily and quickly. It can be used in various algorithms such as the Dynamic Programming solution for Travelling Salesperson Problem to speed up crucial (small) set-based operations.
The visualisation of a bitmask data structure and its operations are shown above.
The top row describes the indices of the bits of the input integer S starting from the 0-th bit as the rightmost bit. Note that we use 1-digit hexadecimal notation of A/B/../E for the 10/11/../14-th bit.
The second row describes the bits of the input integer S. In practical applications, this is usually a 32-bit signed integer (e.g., int in C++/most other programming languages in 2023). Sometimes, this is a 64-bit signed integer (e.g., long long in C++). For this visualization, we limit S to 16-bit signed integer.
The third row describes the bits of the (bit)mask that will be applied to S together with the associated bitwise operation.
The last row describes the result.
Dalam visualisasi ini, kami saat ini mendukung 6 operasi masker bit (semua berjalan dalam O(1)):
Kita bisa memasukkan sebuah bilangan bulat (kecil) diantara [0..32767 (215-1)] dalam Desimal (basis-10) dan bentuk Biner (basis-2) dari S akan divisualisasikan.
Alternatifnya, kita bisa memilh bilangan bulat acak diantara jangkauan yang sama [0..32767], sebuah pangkat 2 acak (dengan pola spesifik '10...0'), atau sebuah pangkat 2 acak dikurangi satu (dengan pola spesifik '11...1').
Kita bisa memasukkan indeks dari Bit ke-j dari S untuk diset (dinyalakan).
Catat bahwa indek dimulai dari 0 tetapi dihitung dari bit yang paling kanan (lihat baris paling atas).
Operasi manipulasi bitnya sederhana: S OR (1 << j).
Menyalakan bit yang sudah menyala tidak akan mengubah apapun.
Kita bisa memasukkan indeks dari Bit ke-j dari S untuk dicek (apakah nyala atau mati).
Catat bahwa indek dimulai dari 0 tetapi dihitung dari bit yang paling kanan (lihat baris paling atas).
Operasi manipulasi bitnya sederhana: S AND (1 << j).
Kita bisa memasukkan indeks dari Bit ke-j dari S untuk dihapus (dimatikan).
Catat bahwa indek dimulai dari 0 tetapi dihitung dari bit yang paling kanan (lihat baris paling atas).
Operasi manipulasi bitnya sederhana: S AND ~(1 << j).
Menghapus bit yang sudah mati tidak akan mengubah apapun.
Kita bisa memasukkan indeks dari Bit ke-j dari S untuk diubah (nyala → mati atau mati → nyala).
Catat bahwa indek dimulai dari 0 tetapi dihitung dari bit yang paling kanan (lihat baris paling atas).
Operasi manipulasi bitnya sederhana: S XOR (1 << j).
Operasi ini tidak membutuhkan masukan. Ini adalah operasi spesial untuk dengan cepat mengidentifikasikan bit terkanan yang menyala dalam S.
Operasi manipulasi bitnya sederhana: S AND (-S).
Catat bahwa didalam Two's complement, -S = NOT(S)+1.
For source code example involving bitmask/bit manipulation, please review: bit_manipulation.cpp | py | java | ml.
To test your understanding about bit manipulation, try our Online Quiz on bitmask topic.
And for more challenging problems involving bitmask/bit manipulation, try the following online judge problems: UVa 11933 - Splitting Numbers and Kattis - bitbybit.
Beyond these simple applications, bitmask frequently used as low-level optimizations in a few advanced algorithms, so get ready when you encounter bitmask as sub-component of the bigger algorithms.