package com.yan.offer;

 /**

  * 题目描述:

  *

  * 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

  *

  * @author Yan

  *

  */

 public class ArrayFindSingleNum {

     public ArrayFindSingleNum() {

     }

     private static int[] arr = new int[] { 2, 4, 3, 6, 3, 2, 5, 5 };

     public static void main(String[] args) {

         ArrayFindSingleNum arrayFindNum = new ArrayFindSingleNum();

         int[] num1 = new int[1];

         int[] num2 = new int[1];

         arrayFindNum.findNumsAppearOnce(arr, num1, num2);

         System.out.println(num1[0] + " " + num2[0]);

     }

     // num1,num2分别为长度为1的数组。传出参数

     // 将num1[0],num2[0]设置为返回结果

     public void findNumsAppearOnce(int[] array, int[] num1, int[] num2) {

         if (array == null || array.length == 0 || array.length == 1) {

             return;

         }

         int sum = 0;

         // 将数组中所有元素进行异或。

         for (int i = 0; i < array.length; i++) {

             sum ^= array[i];

         }

         int temp = sum;

         int flag = 1;

         // 判断异或结果中低位起第一个为1的位，即为flag为1的位。

         while (true) {

             if ((temp & flag) != 0) {

                 break;

             } else {

                 flag = flag << 1;

             }

         }

         int sum1 = 0;

         int sum2 = 0;

         // 利用为1的位将数组中的元素分为两部分，一部分为该位为0的元素，另一部分为该位为1的元素。

         // 因为不相同的两个数的异或值中该位为1，所以这两个数该位是不同的，所以这两个数就被分到了两个不同的部分。

         // 因此，分别将每一部分进行全部异或，最终得到的结果分别为两个不相同的数。

         for (int i = 0; i < array.length; i++) {

             if ((array[i] & flag) != 0) {

                 sum1 ^= array[i];

             } else {

                 sum2 ^= array[i];

             }

         }

         num1[0] = sum1;

         num2[0] = sum2;

     }

 }