异或运算的性质

  • 0^N = N
  • N^N = 0
  • 异或运算满足交换律和结合率

上面的两个性质用无进位相加来理解就非常的容易

常见的进制运算问题

  • n>>1 = n/2

  • n<<1 = n*2

  • n<<1|1 = n*2+1

  • L+((R-L)>>1) = (L+R)/2

  • 交换两个数

    int a = 5, b = 8;
a = a ^ b;
b = a ^ b;
a = a ^ b;

  • 一个数组中只有一种数出现了奇数次，其他数出现了偶数次，怎么找到出现奇数次的数

    public static int oddTimesNum(int[] arr) {
    int eor = 0;
    for (int i = 0; i < arr.length; i++) {
        eor ^= arr[i];
    }
    return eor;
}

  • 把一个int类型的数，提取出来最右侧的1 （0000101011001000）-> (0000000000001000)
    n & (~n + 1)

  • 一个数组中只有两种数出现了奇数次，其他数出现了偶数次，怎么找到这两种数

    public static void oddTimesNum(int[] arr) {
    int eor = 0;
    for (int i = 0; i < arr.length; i++) {
        eor ^= arr[i];
    }
    //eor = a^b
    //eor != 0
    //0110010000 --> 0000010000
    int rightOne = eor & (~eor + 1);

    int a_num = 0;
    for (int i = 0; i < arr.length; i++) {
        //假设a^b在第六为上不同，则rightOne第六位为1，数组中的数可以被分为两份(第六位为1，第六位不为一)
        if ((arr[i] & rightOne) != 0) {
            //找出数组中第六位为0的数
            a_num ^= arr[i];
        }
    }
    int b_num = eor ^ a_num;
    System.out.println(a_num + " " + b_num);
}

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

    public int singleNumber(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int ans = 0;
    for (int i = 0; i < 32; i++) {
        int cnt = 0;//统计该位1的出现次数情况
        int index = 1 << i;
        for (int num : nums) {
            //该位与操作后的结果不为0，则表示该位为1的情况出现了
            if ((num & index) != 0) {
                cnt++;
            }
        }
        //该位上出现1的次数mod3后为1，表示出现一次的数字该位为1
        if (cnt % 3 == 1) {
            ans |= index;
        }
    }
    return ans;
}

状态机解法见https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/cong-zhu-wei-tong-ji-dao-luo-ji-biao-da-shi-fang-s/

  • 获取一个数二进制位1的个数 
    public static int getOneCount(int n) {
    int count = 0;
    while (n != 0) {
        int rightOne = n & (~n + 1);//提取出最右侧的1
        count++;
        n ^= rightOne;//n减去提取过的1
    }
    return count;
}

hhhhh