title: Increase set of numbers so that XOR sum is 0
body: <p>I need some help with a problem that I have reduced to the following. I have N 30 bit numbers, such that the combined XOR of all of them is non-zero. I need to add a non-negative (0 or more) value to each of the N numbers, such that the combined XOR of the new numbers becomes 0, under the constraint that the total addition value (not the number of additions) is minimized.</p>
  
  <p>For example, if I had numbers (01010)<sub>2</sub>, (01011)<sub>2</sub> and (01100)<sub>2</sub> as three numbers (N = 3). Then, their combined XOR is (01101)<sub>2</sub>. We could add some numbers as follows:  </p>
  
  <ul>
  <li>(01010)<sub>2</sub> + (00001)<sub>2</sub> = (01011)<sub>2</sub> : (+1)</li>
  <li>(01011)<sub>2</sub> + (10000)<sub>2</sub> = (11011)<sub>2</sub> : (+16)</li>
  <li>(01100)<sub>2</sub> + (00100)<sub>2</sub> = (10000)<sub>2</sub> : (+4)</li>
  </ul>
  
  <p>Now, the total XOR of the new numbers is 0, and the total addition is 21 (=+1+16+4). This total addition value  has to be <strong>minimized</strong> (there could be a better distribution which reduces this total, but this is just an <em>example</em>).</p>
  
  <p>These numbers are 30 bits each, so the numbers could be large, and N &lt;= 15. I would really appreciate it if someone could show some efficient way to solve this. I suspect a DP solution is possible, but I could not formulate anything.</p>
  
  <p>Thanks!</p>