Xor on sets

#1

very common to see dp on bitmask notation like

dp[i][j] = dp[i - 1][s ^ (1 << j)] + a[x];

or something of the sort. What is the shortcut for xor? Is it short for exclusion of set? How does that work, if so?

#2

Can we have some context as to the problem and relevant solution?

#3

If you don’t know what bitwise operators are, I would highly recommend you go to the usaco guide module to learn them. Also, by the sound of your question, I don’t think you understand how bits/binary and sets work together. You can just research that online.

For your question, s^\wedge(1<<j) is basically the set s, except it doesn’t have j. So j is excluded from set s. This is only if and only if j was previously in set s. If it wasn’t, then the operator adds j to set s. We can check if j is in set s using s\&(1<<j). Here’s an example:

if(s&(1<<j)){
    //Only enters the conditional if j is in set s
    dp[i][j] = dp[i - 1][s ^ (1 << j)] + a[x]
}

I would highly recommend that you try to figure how the XOR operator does this.

Hint

Try to think in bits/binary

Also, another way to write s^\wedge(1<<j) in code is s-(1<<j). As I said before, this only works if and only if j was previously in set s. However, unlike the previous method, if j was not previously in the set, j will not be added to set s. It will just bring up a new and random set that we don’t need. Another way to have set s without j is this method, s\&!(1<<j). This method does not care if j was previously in set s. However, don’t go blindly using this method. Different problems require different techniques. I hope this helps :grin: :slightly_smiling_face: