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.
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.
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.
Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.
In this visualization, we currently support 6 Bitmask operations (all run in O(1)):
- Set S (several ways)
- Set j-th Bit
- Check j-th Bit
- Clear j-th Bit
- Toggle j-th Bit
- Least Significant Bit
Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
We can enter a (small) Integer between [0..32767 (215-1)] in Decimal (base-10) and the Binary (base-2) form of S will be visualized.
Alternatively, we can select any random Integer between the same range [0..32767], a random powers of 2 (with specific pattern of '10...0'), or a random powers of 2 minus 1 (with specific pattern of '11...1').
Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.
We can enter the index of the j-th Bit of S to be set (turned on).
Note that index starts from 0 but counted from the rightmost bit (refer to the top row).
The bitwise operation is simple: S OR (1 << j).
Setting a bit that is already on will not change anything.
We can enter the index of the j-th Bit of S to be checked (on whether it is on or off).
Note that index starts from 0 but counted from the rightmost bit (refer to the top row).
The bitwise operation is simple: S AND (1 << j).
We can enter the index of the j-th Bit of S to be cleared (turned off).
Note that index starts from 0 but counted from the rightmost bit (refer to the top row).
The bitwise operation is simple: S AND ~(1 << j).
Clearing a bit that is already off will not change anything.
We can enter the index of the j-th Bit of S to be toggled (on → off or off → on).
Note that index starts from 0 but counted from the rightmost bit (refer to the top row).
The bitwise operation is simple: S XOR (1 << j).
This operation requires no input. It is a special operation to quickly identify the rightmost bit that is on in S.
The bitwise operation is simple: S AND (-S).
Note that in 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.
You have reached the last slide. Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.
Increment
Set S
Set j-th Bit
Check j-th Bit
Clear j-th Bit
Toggle j-th Bit
Least Significant Bit