码农路上

思路大概是这样的：

因为除了这两个只出现一次的数字外，其余都是成对出现的，有一种运算符，异或运算，两个相同的数字异或之后为0，所以将数组中所有的数字依次异或，结果就是这个两个支出现一次的的数异或的结果；接下来就是如何将他们分开，因为这两个数不相同，所以异或的结果必定不为0，找出这个异或的结果的 二进制表示中第一次出现医德位数，按这个条件，将原来的数组分为两个子数组，然后将他们中的数字依次异或即可得到数组中只出现依次的的两个数。

public static void main(String[] args) {
        int nums[] = new int[]{1,2,3,2,1,5,6,6};
        int bitResult = 0;
        for(int t:nums){
	//所有数字进行异或,最终得到结果就是只出现一次的两个数字的异或结果
            bitResult^=t;
        }
//获取那两个只出现一次的两个数的最后一个不同的二进制位,即异或结果最后一个1(两个数字不同的二进制位)
        int t = bitResult & (-bitResult);
        int nums1=0,
                nums2=0;
        for (int m : nums) {
//使用这个二进制位对原始数组进行分组，分为两组，然后分别拿第一步的异或结果和分组内的所有元素再次异或，就会分别得到那两个只出现一次的数字。
            if ((m & t) == t) {
                nums1 ^= m;
            } else {
                nums2 ^= m;
            }
        }
        System.out.println(nums1 + "  _  " + nums2);

        System.out.println(Integer.toBinaryString(6));
        System.out.println(Integer.toBinaryString(-6));
    }

还有另外一种查找第一个为1的位数办法:

public static  int[] fun(int []a){
     int n=0;
     int[] res = new int[2];
     for(int i=0;i<a.length;i++){
         n^=a[i];
     }
     int index = findFirst1(n);
     for(int i = 0; i < a.length; ++i){
         if(isBit1(a[i], index)){
             res[0] ^= a[i];
            }else{
                res[1] ^= a[i];
            }
        }
        return res;
    }
//找出二进制表示中第一个为1的位数（从右往左的第几位）
    private static int findFirst1(int bitResult){
        int index = 0;
        while(((bitResult & 1) == 0) && index < 32){
            bitResult >>= 1;
            index++;
        }
        return index;
    }
//对原数组进行分类(根据上找出的二进制的第几位上面是否是1来进行分组)
    private static boolean isBit1(int target, int index){
        return ((target >> index) & 1) == 1;
    }
    public static void main(String[] args) {
        int[] a = {3, 2, 5, 8, 4, 2, 3, 7, 5, 8};
        for (int n : fun(a)) {
            System.out.println(n);
        }
    }
}

求负数的二进制: （按位取反再+1）

如果确定了机器的字节长，那么首位就代表符号位，如果首位是0代表这个二进制是整数，如果首位是1，代表这个数是负数。

负数的二进制是取它的补码，补码是这个数字的正数按位取反再加1。

例如-1：先求出它的正数的二进制

1的二进制　 0000 0000 0000 0000 0000 0000 0000 0000

　　　　　　0000 0000 0000 0000 0000 0000 0000 0001

然后取它的反码

　　　　　　1111 1111 1111 1111 1111 1111 1111 1111

　　　　　　1111 1111 1111 1111 1111 1111 1111 1110

然后把反码加1

　　　　　　1111 1111 1111 1111 1111 1111 1111 1111

　　　　　　1111 1111 1111 1111 1111 1111 1111 1111　　这个就是-1的二进制

变形:

题目

　　在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

思路: 将所有数字的二进制表示的对应位都加起来，如果某一位能被三整除，那么只出现一次的数字在该位为0；反之，为1。

public static int findNumberAppearingOnce(int[] arr) {
        if(arr==null || arr.length<=0)
            throw new RuntimeException();
        int[] bitSum = new int[32];
        for(int i=0;i<32;i++)
            bitSum[i]=0;
        for(int i=0;i<arr.length;i++) {
            int bitMask=1;
            for(int j=31;j>=0;j--) {
                int bit=arr[i]&bitMask;  //注意arr[i]&bitMask不一定等于1或者0，有可能等于00010000
                if(bit!=0)
                    bitSum[j]+=1;
                bitMask=bitMask<<1;
            }
        }
        System.out.println(Arrays.toString(bitSum));
        //到这个时候,bitSum数组中每个值，那么能被3整除(出现一次那个数字该位是0)，那么被3整除余1(出现一次那个数字该位是1)
        //按照这个规律已经可以确定出现一次数字的二进制表示是多少，比如如果数组是new int[]{3, 4, 5, 7, 7, 5, 3, 9, 7, 5, 3, 9,9}则bitSum结果是
        //[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 7, 6, 12]
        //根据被三整除得到结果
        //[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0] = 4
        //下面的方法只是将这个二进制还原为十进制
        int result=0;
        for(int i=0;i<32;i++) {
            result=result<<1;
            result+=(bitSum[i]%3);
            //result=result<<1;  //不能放在后面，否则最前面一位就没了
        }
        return result;
    }

注

　1.判断某个数x的第n位（如第3位）上是否为1，

　　1）通过 x&00000100 的结果是否为0 来判断。（不能根据是否等于1来判断）

　　2）通过（x>>3)&1 是否为0 来判断

2.通过以下代码实现二进制转化为数字（注意左移语句的位置）

int result=0;
        for(int i=0;i<32;i++) {
            result=result<<1;
            result+=(bitSum[i]%3);
            //result=result<<1;  //不能放在后面，否则最前面一位就没了
        }

如果一个数组中，只有三个数字出现了一次，其余均出现两次，怎么求这三个数字？
思路:

在这道题中，如果我们能够找出一个只出现一次的数字，剩下两个只出现一次的数字就很容易找出来了。

如果我们把数组中所有数字都异或起来，那最终的结果（记为x）就是a、b、c三个数字的异或结果（x=a^b^c）。其他出现了两次的数字在异或运算中相互抵消了。

我们可以证明异或的结果x不可能是a、b、c三个互不相同的数字中的任何一个。我们用反证法证明。假设x等于a、b、c中的某一个。比如x等于a，也就是a=a^b^c。因此b^c等于0，即b等于c。这与a、b、c是三个互不相同的三个数相矛盾。

由于x与a、b、c都各不相同，因此x^a、x^b、x^c都不等于0。

我们定义一个函数f(n)，它的结果是保留数字n的二进制表示中的最后一位1，而把其他所有位都变成0。比如十进制6表示成二进制是0110，因此f(6)的结果为2（二进制为0010）。f(x^a)、f(x^b)、f(x^c)的结果均不等于0。

接着我们考虑f(x^a)^f(x^b)^f(x^c)的结果。由于对于非0的n，f(n)的结果的二进制表示中只有一个数位是1，因此f(x^a)^f(x^b)^f(x^c)的结果肯定不为0。这是因为对于任意三个非零的数i、j、k，f(i)^f(j)的结果要么为0，要么结果的二进制结果中有两个1。不管是那种情况，f(i)^f(j)都不可能等于f(k)，因为f(k)不等于0，并且结果的二进制中只有一位是1。

于是f(x^a)^f(x^b)^f(x^c)的结果的二进制中至少有一位是1。假设最后一位是1的位是第m位。那么x^a、x^b、x^c的结果中，有一个或者三个数字的第m位是1。

接下来我们证明x^a、x^b、x^c的三个结果第m位不可能都是1。还是用反证法证明。如果x^a、x^b、x^c的第m位都是1，那么a、b、c三个数字的第m位和x的第m位都相反，因此a、b、c三个数字的第m位相同。如果a、b、c三个数字的第m位都是0，x=a^b^c结果的第m位是0。由于x和a两个数字的第m位都是0，x^a结果的第m位应该是0。同理可以证明x^b、x^c第m位都是0。这与我们的假设矛盾。如果a、b、c三个数字的第m位都是1，x=a^b^c结果的第m位是1。由于x和a两个数字的第m位都是1，x^a结果的第m位应该是0。同理可以证明x^b、x^c第m位都是0。这还是与我们的假设矛盾。

因此x^a、x^b、x^c三个数字中，只有一个数字的第m位是1。于是我们找到了能够区分a、b、c三个数字的标准。这三个数字中，只有一个数字满足这个标准，而另外两个数字不满足。一旦这个满足标准数字找出来之后，另外两个数字也就可以找出来了。