Find Odd Integer Singleton
by Isai Damier, Android Engineer @ Google

/****************************************************************************
 * Author: Isai Damier
 * Title: Find Odd Singleton
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Given an int array where all values occur an even number of times;
 *   except for one value, which occurs an odd number of times and which we
 *   shall call a singleton; find the singleton.
 *
 * Sample Input: {1,2,7,3,4,5,7,6,7,4,2,6,3,1,5}
 * Sample Output: 7
 *
 * Technical Details:
 *   The most efficient approach is to XOR all the elements of the array and
 *   return the result. Recall from digital logic the following truths about
 *   the XOR (^) operator: x^x = 0; 0^x = x.
 *   (Ref http://www.teahlab.com/basicGates/xorgate).
 *
 ***************************************************************************/ 
 public int findOddSingleton(int[] a) {
  int i = a[0];
  for (int n = 1; n < a.length; n++) {
    i ^= a[n];
  }
  return i;
}

import org.junit.Test;
import static org.junit.Assert.*;

public class BitwiseTest {

 /**
   * Test of findOddSingleton method, of class Bitwise.
   */
  @Test
  public void testFindOddSingleton_int() {
    System.out.println(""findOddSingleton"");
    int iArr[] = {1, 2, 7, 3, 4, 5, 7, 6, 7, 4, 2, 6, 3, 1, 5};
    Bitwise bits = new Bitwise();
    assertEquals(7, bits.findOddSingleton(iArr));
  }
}