Xor on sets

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?

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

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:

    //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.


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: