Single Number III

    1. public class Solution {
    2.     /**
    3.      * @param A : An integer array
    4.      * @return : Two integers
    5.      */
    6.         ArrayList<Integer> nums = new ArrayList<Integer>();
    7.         if (A == null || A.length == 0) return nums;
    9.         int x1xorx2 = 0;
    10.         for (int i : A) {
    11.             x1xorx2 ^= i;
    12.         }
    14.         // get the last 1 bit of x1xorx2, e.g. 1010 ==> 0010
    15.         int last1Bit = x1xorx2 - (x1xorx2 & (x1xorx2 - 1));
    16.         int single1 = 0, single2 = 0;
    17.         for (int i : A) {
    18.                 single1 ^= i;
    19.             } else {
    20.                 single2 ^= i;
    21.             }
    22.         }
    24.         nums.add(single1);
    25.         nums.add(single2);
    26.         return nums;
    27.     }
    28. }