位运算 - oneslideicywater/algor GitHub Wiki

一组数中，所有数都出现N次，只有一个数出现一次

我们换一个角度来看，如果数组中没有x，那么数组中所有的数字都出现了3次，在二进制上，每位上1的个数肯定也能被3整除。

Code

public class Main {

    public static void main(String[] args) {

            int a[] = {5,2,3,3,2 };
            for (int j = 0; j < a.length; j++) {
                System.out.print(a[j]);
            }
            System.out.println();
            System.out.println(findNumber(a, a.length));



    }

    public static int findNumber(int a[], int n) {
        int bits[] = new int[32];
        Arrays.fill(bits, 0);
        int i, j;
        for (i = 0; i < n; i++)
            for (j = 0; j < 32; j++)
                bits[j] += ((a[i] >> j) & 1);
        // 如果某位上的结果不能被整除，则肯定目标数字在这一位上为
        int result = 0;
        for (j = 0; j < 32; j++)
            if (bits[j] % 2 != 0)
                result += (1 << j);
        return result;
    }
}

异或

两个相同的数，异或为0.异或可以过滤掉偶数次出现的数。

public class Main {

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        scanner.nextLine();
        int[] a=new int[n];
        for (int i = 0; i <n ; i++) {
            a[i]=scanner.nextInt();
        }
        System.out.println(groupXor(a));
    }

    public static int xor(int a,int b){
        return a^b;
    }

    public static int groupXor(int[] a){
        int result=a[0];
        for (int i = 0; i < a.length-1; i++) {
           result=result ^ a[i+1];
        }
        return result;
    }

}

二进制数字的相互转化

   public static int[] transformToBits(int oper){
        int[] bits=new int[32];
        for (int i = 0; i <32 ; i++) {
            bits[i]=(oper>>i)&1;
        }
        return bits;
   }

  public static int transformBitsToInt(int[] oper){
        int sum=0;
        for (int i = 0; i < 31; i++) {
            sum+=oper[i]<<i;
        }
        return sum;
  }

如何判断一个数是不是2的幂？ 转化为二进制数后，只有一个位是1。 如何判断一个数是不是2^n的幂？ 在满足是2的幂的条件下，32bit分成自组，如果有个位在小组第3位就是4的幂。

⚠️ **GitHub.com Fallback** ⚠️