Bitmasks

A bitmask stores a set of items in one integer: bit $i$ is 1 if item $i$ is in the set. One int holds up to 31 items and a long long up to 63. Because every set is a number, one loop over the numbers from $0$ to 2^n - 1 goes through every subset, which solves "try every subset" problems with n \le 20 without recursion.

Explanation

You have 5 coins, and the shop sells bread for 2, milk for 3 and cheese for 5. Which baskets cost exactly 5 coins?

To list every basket without missing one, write a row of three marks: 1 if the item is taken, 0 if it is left. We write cheese on the left and bread on the right. Fill the rows the way you would by hand: the bread mark changes every row, the milk mark every 2 rows, the cheese mark every 4 rows. This gives 8 rows, one per basket.

Fig. 1. Every basket of three items, one per row: 1 means the item is taken. The prices 5, 3 and 2 head the columns of cheese, milk and bread, and the last column is the cost.

Two baskets cost 5: milk and bread (2 + 3 = 5), and cheese alone. As a program, this is three nested loops, one per item, each going over "leave" and "take".

The next shop has two more shelves, apples for 4 coins and juice for 7, and now you have 11 coins. Five nested loops would do for this shop. But in a real problem the first number of the input says how many items there are, and the next test may have 6 items, or 17.

How can one loop go through every basket, however many items there are? Look at Fig. 1 again, and read each row of marks as a number written with only the digits 0 and 1. In ordinary numbers the places from the right are worth 1, 10 and 100, and here they are worth 1, 2 and 4. Row 101 is then 4 + 1 = 5, and the 8 rows are the numbers 0 to 7, in order. Writing numbers this way is called binary. Counting in binary changes the last digit every step, the next digit every 2 steps and the next every 4 steps, which is exactly how we filled the table.

To go back from a number to its digits, take the largest place value that fits, write 1 there, subtract it, and repeat with what is left. For 6, the 4 fits (2 left), then the 2 fits (0 left), so 6 = 110: cheese and milk. Fig. 2 shows both directions on the basket of cheese and bread.

Fig. 2. The basket of cheese and bread: prices on top, marks in the middle, place values below. Adding the place values of the taken items gives 4 + 1 = 5, and the binary digits of 5 give back the basket, 101.

Each of the five items is taken or left, so there are 2 · 2 · 2 · 2 · 2 = 32 baskets. Count from 0 to 31 and write each number in binary with 5 digits, worth 1, 2, 4, 8 and 16 from the right. Each number is one basket of the 5-item shop, with bread in the digit worth 1 and juice in the digit worth 16. For example, in 24 the 16 fits (8 left), then the 8 (0 left), so 24 = 11000: juice and apples, 7 + 4 = 11. With 6 items the loop counts to 63, and each further item doubles the count again.

A number whose binary digits say which items are taken is a bitmask (also written "bit mask", or just "mask"). From here on, a basket, or any choice of some of the items, is called a set.

Fig. 3 runs this loop on the 5-item shop.

0 = 00000: the empty basket, which costs 0.

1 = 00001: bread, which costs 2.

2 = 00010: milk, which costs 3. 2 digits change at once.

3 = 00011: bread and milk, which cost 5.

4 = 00100: cheese, which costs 5. 3 digits change at once.

5 = 00101: bread and cheese, which cost 7.

6 = 00110: milk and cheese, which cost 8. 2 digits change at once.

7 = 00111: bread, milk and cheese, which cost 10.

8 = 01000: apples, which costs 4. 4 digits change at once.

9 = 01001: bread and apples, which cost 6.

10 = 01010: milk and apples, which cost 7. 2 digits change at once.

11 = 01011: bread, milk and apples, which cost 9.

12 = 01100: cheese and apples, which cost 9. 3 digits change at once.

13 = 01101: bread, cheese and apples, which cost 11. That is exactly 11, so 13 joins the list.

14 = 01110: milk, cheese and apples, which cost 12. 2 digits change at once.

15 = 01111: bread, milk, cheese and apples, which cost 14.

16 = 10000: juice, which costs 7. 5 digits change at once.

17 = 10001: bread and juice, which cost 9.

18 = 10010: milk and juice, which cost 10. 2 digits change at once.

19 = 10011: bread, milk and juice, which cost 12.

20 = 10100: cheese and juice, which cost 12. 3 digits change at once.

21 = 10101: bread, cheese and juice, which cost 14.

22 = 10110: milk, cheese and juice, which cost 15. 2 digits change at once.

23 = 10111: bread, milk, cheese and juice, which cost 17.

24 = 11000: apples and juice, which cost 11. 4 digits change at once. That is exactly 11, so 24 joins the list.

25 = 11001: bread, apples and juice, which cost 13.

26 = 11010: milk, apples and juice, which cost 14. 2 digits change at once.

27 = 11011: bread, milk, apples and juice, which cost 16.

28 = 11100: cheese, apples and juice, which cost 16. 3 digits change at once.

29 = 11101: bread, cheese, apples and juice, which cost 18.

30 = 11110: milk, cheese, apples and juice, which cost 19. 2 digits change at once.

31 = 11111: bread, milk, cheese, apples and juice, which cost 21. That was the last number: only 13 and 24 cost 11.

1/32

Fig. 3. Bread changes at every step, milk every 2 and cheese every 4. The changed digits are outlined, and a number that costs 11 joins the list on the right.

Only two baskets cost exactly 11: 13 (bread, cheese and apples) and 24 (apples and juice).

Two sets at once

A week fits in 7 binary digits: Monday is the rightmost digit and Sunday the leftmost, and a 1 means "free that day". Ann is free on Monday, Wednesday, Friday and Saturday, which is 0110101 = 53. Ben is free on Wednesday, Thursday, Saturday and Sunday, which is 1101100 = 108. One operation compares all seven days at once. a & b keeps a 1 where both numbers have a 1: the days both are free. a | b keeps a 1 where at least one has a 1, and a ^ b where exactly one has a 1. ~b turns every 0 of b into 1 and every 1 into 0, so a & ~b gives the days Ann is free and Ben is busy.

Fig. 4. Ann's week a, Ben's week b and the results of a & b, a | b and a ^ b. Monday is the rightmost digit.

Implementation

In code, a binary digit is a bit. Bits are numbered from the right, starting at 0, and bit i is worth 2^i. The items are numbered from 0 to n - 1 in the order of the input: bread is item 0, milk 1, cheese 2, apples 3 and juice 4. Item i is bit i, so 13 = 01101 is the set of items 0, 2 and 3.

1 << i shifts a 1 left by i bits: it writes i zeros after the 1. So 1 << 0 is 1, 1 << 1 is 10 = 2, 1 << 2 is 100 = 4, and then come 8 and 16. 1 << i is 2^i, the value of bit i, and 1 << n is 2^n, the number the loop counts up to. An int has 32 bits, but its leftmost bit is the sign: a 1 there makes the number negative. So only bits 0 to 30 are safe for items, and 1 << 31 overflows (the result is undefined; common compilers give $-2147483648$).

mask >> i shifts right by i bits: the last i bits drop off, and bit i becomes bit 0. Then & 1 keeps only bit 0, because 1 has its only 1 in bit 0. Together, mask >> i & 1 is bit i of mask. Fig. 5 shows it with mask = 13 = 01101 and i = 2: 13 >> 2 is 011 = 3, and 3 & 1 is 1, so cheese is in the set. Shifts are done before &, so this needs no parentheses.

Fig. 5. Left, 13 = 01101 with bit i = 2; middle, 13 >> 2 = 00011 = 3; right, 3 & 1 = 1. Shifting right by 2 brings bit 2 (cheese) to the end, and & 1 keeps only that bit.

The algorithm for "go through all sets of n items" is:

1. Number the items from 0 to n - 1; item i is bit i, worth 2^i.

2. Go through all numbers mask from $0$ to 2^n - 1.

3. Read the set: item i is in the set if mask >> i & 1 is 1.

4. Test the set: compute what the problem needs (here the cost) and test it.

5. Record the answer.

The program reads n and the target T, then n prices into an array price. It prints each set that costs exactly T on its own line, as its item numbers in increasing order, and then the number of such sets. For the 5-item shop the input is (the comments in the program name the steps above):

5 11
2 3 5 4 7

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, T;
    cin >> n >> T;
    vector<int> price(n);                             // number the items: item i is bit i
    for (int i = 0; i < n; i++) cin >> price[i];

    int found = 0;
    for (int mask = 0; mask < (1 << n); mask++) {   // go through all numbers
        int sum = 0;
        for (int i = 0; i < n; i++)
            if (mask >> i & 1) sum += price[i];       // read the set
        if (sum == T) {                               // test the set
            for (int i = 0; i < n; i++)               // record the answer
                if (mask >> i & 1) cout << i << ' ';
            cout << '\n';
            found++;
        }
    }
    cout << found << '\n';
}

On this input, mask 13 is printed as its items 0, 2 and 3, and mask 24 as items 3 and 4: the two sets the loop found in Fig. 3.

The outer loop runs 2^n times and the inner loop n times for each mask, so the program takes O(2^n \cdot n) time and $O(n)$ memory. Each extra item doubles the time: n = 20 is about 2 \cdot 10^7 steps, well under a second, but n = 30 is about 3 \cdot 10^{10}, too slow.

Changing one item

With 1 << i as the second number, the operations from Fig. 4 change one item. The table shows each one on 18 = 10010 (milk and juice):

The last line needs parentheses, because - is done before <<. Without them, 1 << n - 1 is 1 << 4 = 16 for n = 5, not 31.

Counting the items

__builtin_popcount(mask) returns the number of 1 bits in mask, which is the number of items in the set. It works in GCC and Clang. For example, to look only at sets of exactly 2 items, put this line at the top of the outer loop; continue skips to the next mask:

if (__builtin_popcount(mask) != 2) continue;

Of the 32 masks of 5 items, 10 have exactly two bits set, and only mask 24 costs 11.

Common mistakes

• Writing 2 ^ n for 2^n, but in C++ ^ is the bit operation from Fig. 4, so 2 ^ 5 is 7. Write 1 << n.

• Forgetting that == and != are done before &, so if (mask & 1 << i != 0) means mask & ((1 << i) != 0), which is mask & 1. Write if (mask >> i & 1).

• Treating mask & 1 << i as 0 or 1, when it is 0 or 2^i. Compare with != 0 in parentheses, or count with __builtin_popcount.

• Numbering the items from 1 while bits start at 0, so the last item's bit is never set below 1 << n and bit 0 is never read. Number the items from 0, or check mask >> (i - 1) & 1.

• Using int shifts with a long long mask, as in y |= 1 << 35, where the shift is still done in int and the result is undefined. Write 1LL << i, and count with __builtin_popcountll.

Similar techniques

Backtracking also lists all subsets, with a recursive function that decides one item at a time. Use it when an early choice can rule out a whole branch, such as stopping once the cost passes 11; a mask loop always visits all 2^n numbers.

Meet in the middle handles up to about 40 items, where 2^{40} masks are too many. It splits the items in two halves, lists the 2^{20} masks of each half and combines the two lists.

A mask is a number from $0$ to 2^n - 1, so it can be an index into an array of size 2^n. Dynamic programming over subsets fills such an array, best[mask], from smaller masks. It solves "best order to visit all places" problems with n \le 20.

A state graph uses a mask as part of a search state, such as the room you are in plus the keys you carry.

Practice