Single Number

Problem:

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution:

1:  public class Solution {  
2:    public int singleNumber(int[] A) {  
3:      for(int i=1;i<A.length;i++)  
4:        A[i]^=A[i-1];  
5:      return A[A.length-1];  
6:    }  
7:  }  

Discussion:
Use bitwise OR operator ^. Definition is as follows.

A bitwise XOR takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. In this we perform the comparison of two bits, being 1 if the two bits are different, and 0 if they are the same. For example:

    0101 (decimal 5)
XOR 0011 (decimal 3)
  = 0110 (decimal 6)

The bitwise XOR may be used to invert selected bits in a register (also called toggle or flip). Any bit may be toggled by XORing it with 1. For example, given the bit pattern 0010 (decimal 2) the second and fourth bits may be toggled by a bitwise XOR with a bit pattern containing 1 in the second and fourth positions:

    0010 (decimal 2)
XOR 1010 (decimal 10)
  = 1000 (decimal 8)