title: Bit Manipulation and XOR
body: <p>I have an Question regarding bit manipulation in Algorithms.</p>
  
  <p>Given an array of integers, every element in array appears thrice except for one element which occurs only once. Find that element which appear only once.</p>
  
  <p>Example:  </p>
  
  <pre><code>Input : [1, 2, 4, 3, 3, 2, 2, 3, 1, 1]  
  Output : 4
  </code></pre>
  
  <p>I came across solution using <code>XOR</code> but I am not able to understand it. Below is solution:</p>
  
  <pre><code>int singleNumber(vector&lt;int&gt; A) {
      int first = 0;
      int second = 0;
      for(auto n:A){
          first = (first ^ n) &amp; ~second;
          second = (second ^ n) &amp; ~first;
      }
      return first;
  }
  </code></pre>
  
  <p>Can someone explain how below 2 lines of code works?</p>
  
  <pre><code>first = (first ^ n) &amp; ~second;
  second = (second ^ n) &amp; ~first;
  </code></pre>
  
  <p><strong><em>[Edited]</em></strong></p>
  
  <p>I had included <code>cout&lt;&lt;first&lt;&lt;" "&lt;&lt;second&lt;&lt;endl;</code> for every iteration in loop but it is showing following output which I am not able to understand. How this lead to solution?</p>
  
  <pre><code>1 0
  3 0
  7 0
  4 3
  4 0
  6 0
  4 2
  5 0
  4 1
  4 0
  </code></pre>