Bitmask provide an efficient way to manipulate a small set of Booleans.
By using bitwise operations, Boolean flags 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 Salesman Problem to speed up crucial (small) set-based operations.
Click 'Next' (on the top right)/press 'Page Down' to advance this e-Lecture slide, use the drop down list/press 'Space' to jump to a specific slide, or Click 'X' (on the bottom right)/press 'Esc' to go to Exploration mode.
The visualisation of a bitmask data structure and its operations are shown above.
The top row describes the bits of the input integer S.
The middle row describes the bits of the mask j that will be applied to S together with the associated bitwise operation.
The last row describes the result New S.
Pro-tip: Since you are not logged-in, you may be a first time visitor who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown] to advance to the next slide, [PageUp] to go back to the previous slide, [Esc] to toggle between this e-Lecture mode and exploration mode.
In this visualization, we currently support 6 Bitmask operations (all runs in O(1)):
Another pro-tip: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2017). 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.
For source code example involving bitmask/bit manipulation, download ch2_03_bit_manipulation.cpp/java (from the Competitive Programming book website).
To test your understanding about bit manipulation, try our Online Quiz on bitmask topic.
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
Control the animation with the player controls! Keyboard shortcuts are:
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.