异或运算

不同为 1 相同为0 (也可以理解为无进位相加) （相当于在或运算加了（1）相同为0的限制）

  • 使用异或运算交换数据

    1. // 交换数据
    2. // 前提 arr[i] 和 arr[j]    不指向同一个内存地址 否则会等级0
    3. arr[i] = arr[i]^arr[j]  
    4. arr[j] = arr[i]^arr[j]
    5. arr[i] = arr[i]^arr[j]

  • 取得最右侧的1

    1. N & (~N + 1)
    2.   证明:
    3. N: 10000100
    4.   ~N: 01111011
    5.     ~N + 1: 0111111
    6.       N & (~N + 1) : 00000100

  • 任何数异或自身都等于0

  • 任何数异或0都等于自身

  • 有交换性 和结合性

    1. 0 ^ 0 = 0
    2. 1 ^0 = 1
    3. x ^ y = y ^ x
    4. (x ^ y) ^ z = x ^ (y ^ z)

  • 可以用来做些简单的加密过程

    • 通过明文和密钥进行异或运算 得到密文

    • 密文和明文进行异或运算 得到密钥

      1. text ^ key = cipherText
      2. cipherText ^ key = text

      或运算

      & 或运算符 只有两个相同才会相同 （理解为两个都要相同）
      只有两个都为1的时候 才会为1

      1. 1 & 2 = 0
      2. 1 & 0 = 0

      与运算

      ｜ 与运算符 只有两个有一个为1 则是1 （理解为只要有一个为1就是1）
      只有两个都是0 才是0

      1. 1 | 0 = 1

      题目

      一个数组中 有两种数字出现了奇数次 其他数都出现了偶数次 怎么找出并打印这两个数字

      1. public static void searchOdd(int arr[]) {
      2.    int flag = 0; // 0 异或任何数都等他们本身
      3.    for (int i = 0; i <arr.length ; i++) {
      4.        flag ^= arr[i];
      5.    }
      6.    // 此时falg 为 a ^ b
      7.    int rightOne = flag & ((~flag) + 1);
      8.    int resultOne= 0,resultTwo = 0;
      10.    // rightOne 为最右侧的一个1 因为有两个数为奇数而且不等则他们一定有一位数不相同 且 这个1就是他们(a^b)最先不同的位数
      11.    for (int i = 0; i < arr.length; i++) {
      12.        // 确定这一位上为1
      13.        if((rightOne & arr[i]) !=0) {
      14.            resultOne ^=arr[i];
      15.        }else {
      16.            // 确定这一位上为0
      17.            resultTwo ^= arr[i];
      18.        }
      19.    }
      20.    System.out.println(resultOne);
      21.    System.out.println(resultTwo);
      22. }

      一个数中的1的个数有多少个

      1. public static int oneNumbers(int number) {
      2.    int count = 0;
      3.    int flag = 0;
      4.    while (number != 0) {
      5.        flag = number & ((~number) + 1);
      6.        count++;
      7.        // 将这个1重置为0
      8.        number = flag ^ number;
      9.    }
      10.    return count;
      11. }

      右移运算符

      1. int middle = (int) pre +((next - pre) >> 1)
      2. // >> 1相当于除了一个2