In computer science, a bit mask is a binary number that represents something. It’s used for bitwise operations, especially in a bit field. A bit mask can set multiple bits in a byte, nibble, or word to on or off, or invert them from on to off.
Bit masks are useful for:
- Storing data compactly
- Accessing specific bits in a byte of data
- Solving difficult problems
Bit masking is based on boolean logic. For example, the binary representation of the number 11 is “1011”. This is because in base 2, 11 = 8 + 2 + 1.
Medium Article
Do you have to know Bit Manipulation and Bitmask for the coding interview?
These two topics are considered advanced materials and are “implicitly” not required for the coding interview. Nevertheless, it is entirely within the interviewer’s rights to give you these questions, should they feel like it.
This is a brief overview of all the standard techniques and patterns you should know for handling bitmask problems.
Table of Contents
· The Basic
∘ Common Operations for Bit Manipulation
∘ Important Operations for Bitmasks
· Bit Manipulation Patterns
∘ Count the number of 1bits in the binary representation of a number
∘ Check if a positive number is a power of two
∘ Efficiently compute Pow(x, n), where x > 0 and n > 0
· Bitmask Pattern
∘ General pattern:
∘ Given an array of unique elements, find all possible subsets
∘ Count all possible subsets of size k that sum to a given target
· Conclusion
All codes and equations were written by author.
The Basic
Bitmask is the idea of using the binary representation of numbers to solve otherwise difficult problems. This representation is unique for each number.
Example: The bits of the number 11 is “1011”, because in base 2:
11 = 8 + 2 + 1 = 1 * 2³ + 0 * 2² + 1 * 2¹ + 1 * 2⁰= “1011”
When dealing with bitmask: It does not matter what the actual number is. All we should care about is its binary form and the following operations:
Common Operations for Bit Manipulation
- Left Shift: to shift x to the left by n spaces, we use x << n. For example, in binary form, “1011” << 3 = “1011000” , or 11 << 3 = 88.
- Right Shift: similarly, we use x >> n . For example, “10101” >> 3= “101” (note that the 1bits get vanished).
- Clear the lowest set bit: x & (x — 1) (e.g. “10100” → “10000” )
- AND: a & b = 1 if a = 1 AND b = 1, else 0
- OR: a | b = 1 if a = 1 OR b = 1, else 0
- XOR: a ^ b = 1 if exactly one of a or b is 1, else 0
- For numbers greater than 1, we apply these operations iteratively to each bit position. E.g. “10111” AND “1100” = “00100” = “100”
Important Operations for Bitmasks
- Turn the i^th bit to 1: mask = mask | (1 << i) , or mask |= (1 << i)
- Flip the i^th bit: mask = mask ^ (1 << i) , or mask ^= (1 << i)
Most of the time, you will be manipulating a number called mask . This mask will be used to keep track of the “used” or “unused” elements in a list.
Example: Given a set of 3 elements A = {1,2,3}, how do we effectively represent all the subsets of this set?
Answer: Use numbers from 0 to 7 and their corresponding bitmasks, where each 1bit position signals to a chosen element:
0 = “000” = {} = the empty set
1 = “001” = {1}
2 = “010” = {2}
3 = “011” = {1, 2}
4 = “100” = {3}
5 = “101” = {1, 3}
6 = “110” = {2, 3}
7 = “111” = {1, 2, 3}
In general, given a set of n elements, we can always represent all the subsets of this set using numbers from 0 to 2^n — 1.
And this is the basic idea of bitmask. We will manipulate a mask that represents a current subset of a given list.
Bit Manipulation Patterns
Count the number of 1bits in the binary representation of a number
We can keep shifting the number to the right until it becomes zero. At each step, we check if the 0^th bit is one, and add it to the total count:
We can optimize this solution further: instead of shifting by 1bit each time, we can remove the lowest set bit and shift accordingly:
Check if a positive number is a power of two
If n is a power of two, then for some positive integer k,
In other words, the binary representation of n has the form “100…0” . Then we can easily verify this by removing the lowest bit set of n:
Efficiently compute Pow(x, n), where x > 0 and n > 0
Consider the binary representation of n, using 11 as an example:
Notice that each position in the binary representation of 11 corresponds to an exponent of the form x, x², x⁴, …
So, instead of looping and multiplying n times to compute the answer, we can optimize the computation by only storing the power-of-2 powers: x, x², x⁴, x⁸,… and multiply the appropriate values to get our final answer:
Bitmask Pattern
Recall that a mask represents a subset.
For example, I have a mask that reads “00110011”
What is this number in decimal form?
I don’t know, and I don’t care.
All we need to know is that this mask represents a state of a set. This particular mask means we are processing a subset with elements at indices 0, 1, 4, and 5 (going right to left).
General pattern:
What is this piece of code doing?
We loop over all the indices in the set. If we encounter an “unused” element at the index i, then the corresponding mask element will be “0” . Thus not mask at index i is “1”, and so not mask & (1 << i) will return True. Then we can add this element to our subset and process it next.
Given an array of unique elements, find all possible subsets
Recall from the previous section: Given a set of size n, we can use numbers from 0 to 2^n-1 to represent all the subsets.
For each number, we construct the corresponding subset by looking at its binary representation and find the position of all “1” . Then we can add the subset to our final result.
Example output:
A = [1,3,5,7]
subset(A)
[[], [1], [3], [1, 3], [5], [1, 5], [3, 5], [1, 3, 5], [7], [1, 7], [3, 7], [1, 3, 7], [5, 7], [1, 5, 7], [3, 5, 7], [1, 3, 5, 7]]Count all possible subsets of size k that sum to a given target
This problem is Combination Sum III on Leetcode. We want to find all the subsets of size k that sum up to n, such that:
- Only numbers 1 through 9 are used.
- Each number is used at most once.
This problem can be done using back-tracking, but I want to present a bitmask solution here. Once you are comfortable with bit manipulation, you may find that it is easier to solve and/or write solutions using bitmasks.
Our starting mask is 0, representing the empty set (this will be the case 99% of the time). At each step, we choose to turn on any bit at positions 1 to 9 (from right to left, with starting position indexed 0).
For example, “1010101010” has “1” at positions 1, 3, 5, 7, and 9. This mask represents the set {1,3,5,7,9}, with a sum equal to 25.
We can solve the problem using Bitmask and DP. Once we have the set of all valid masks, we can decode each mask and get the final set of numbers.
Here is a solution that utilizes three different bit manipulation techniques discussed in this post:
Conclusion
Bitmask doesn’t have to be intimidating.
When I started prepping for the coding interview, I found bitmask to be the most challenging topic. At first, I would completely skip these questions. However, as I solve more and more problems, I eventually learned that it was not as scary as I had imagined it to be.
Some of my friends did get asked problems about bitmask during their interviews (at some Big Tech). The difficulty level is similar to the two problems presented in the Bitmask Pattern section. The questions were intended to be solved with back-tracking. But, solving with bitmask is a great way to impress the interviewers!
(Chances are, they are not very comfortable with it either.)