Shortest hamiltonian path with dynamic programming and bitmasking

Question

I've just read an article about how to find the shortest hamiltonian path using dynamic programming here http://codeforces.com/blog/entry/337.

While the pseudocode works, I do not understand why I have to take to use the xor operator on the set and 2^i.

Why wouldn't you just substract the current visisted city from the bitmask? What does the xor with the set in order to make the algorithm do it's magic?

To clarify here is the piece of pseudocode written in java:

public int calculate(int set, int i){

        if(count(set) == 1 && (set & 1<<i) != 0){
            return 0;
        }

        if ( dp[set][i] != infinity){
            return dp[set][i];
        }

        for (int city=0;city<n;city++){
            if((set & 1<<city) == 0) continue;
            dp[set][i] = Math.min(dp[set][i], calculate(set ^ 1<<i, city) + dist[i][city]);
        }
        return dp[set][i];
    }

Answer 1

Found the solution to my problem, the ^ is a bitflip. Thus if you have a bitmask and use the xor operator on the mask, you flip the bit on that place. E.g. 1010 ^ (1<<1) results in 1000. Same goes for 1000 ^ (1<<1) = 1010.

The substraction also works, but with the xor operator you know for certain that you only touch the bit at that place, and none else. Image 1000 - (1<1), thus would result in something entirely different. Thus substraction works and can be used if you are 100% sure that at an 1 is at place i, but xor is safer.