title: Shortest hamiltonian path with dynamic programming and bitmasking
body: <p>I've just read an article about how to find the shortest hamiltonian path using dynamic programming here <a href="http://codeforces.com/blog/entry/337" rel="nofollow">http://codeforces.com/blog/entry/337</a>.</p>
  
  <p>While the pseudocode works, I do not understand why I have to take to use the xor operator on the set and 2^i.</p>
  
  <p>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?</p>
  
  <p>To clarify here is the piece of pseudocode written in java:</p>
  
  <pre><code>public int calculate(int set, int i){
  
          if(count(set) == 1 &amp;&amp; (set &amp; 1&lt;&lt;i) != 0){
              return 0;
          }
  
          if ( dp[set][i] != infinity){
              return dp[set][i];
          }
  
          for (int city=0;city&lt;n;city++){
              if((set &amp; 1&lt;&lt;city) == 0) continue;
              dp[set][i] = Math.min(dp[set][i], calculate(set ^ 1&lt;&lt;i, city) + dist[i][city]);
          }
          return dp[set][i];
      }
  </code></pre>