参考代码： https://github.com/njZhuMin/algorithm-practice

异或运算

• 异或运算：相同为 0，不同为 1
• 同或运算：相同为 1，不同为 0

异或运算可以简记成无进位相加。

异或运算的性质

1. 0 ^ N = N; N ^ N = 0
2. 异或运算满足交换律与结合律。

异或奇偶性应用

交换两个数

利用异或运算交换律与结合律的性质，我们可以不借助额外变量来交换两个数。

void swap(int a, int b) {
    // 假设 a = x; b = y
    a = a ^ b;
    // 1. 交换后 b 不变，a = x ^ y; b = y
    b = a ^ b;
    // 2. 交换后 a 不变，a = x ^ y; b = (x ^ y) ^ y = x
    a = a ^ b;
    // 3. 交换后 b 不变，a = (x ^ y) ^ x = y; b = x
}

注意，当 a 和 b 指向同一个内存地址的时候，不能正确交换。

当然这个技巧属于 Nice to know，平时写代码的时候不太建议这么写，大可不必过于炫技。

只出现一次的数字

从异或运算的性质扩展得出，如果一个数出现了偶数次，全部求异或结果就为 0 。因此异或运算常常用来挑选数字。

LeetCode 136 - Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1
Example 2:

Input: [4,1,2,1,2]
Output: 4

public class Q136_SingleNumber {

    public static void main(String[] args) {
        int[] arr1 = new int[]{2, 2, 1};
        int[] arr2 = new int[]{4, 1, 2, 1, 2};
        System.out.println(singleNumberWithXor(arr1));
        System.out.println(singleNumberWithXor(arr2));
    }

    static int singleNumberWithXor(int[] arr) {
        int xor = 0;
        for (int i : arr) {
            xor = xor ^ i;
        }
        return xor;
    }
}

提取二进制最右侧的 1

int result = N & (~N + 1)

两个只出现一次的数

LeetCode 260 - Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example:

Input:  [1,2,1,3,2,5]
Output: [3,5]
Note:

The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

假设数列中，只出现一次的两个数分别为 a 和 b，且不相等。

我们先按照常规思路，对所有元素求异或运算，得到 xor = a ^ b 。因为 a ≠ b，因此 xor ≠ 0，其二进制必然至少有一个 1 。

假设 a 在第 N 位为 1，b 在第 N 位上为 0 。如果我们把数组中，每一个第 N 位置上为 1 的元素全部求异或，所有的 b 就必然被排除在运算以外。其他出现偶数次的数也被约掉，最后就能得到 a 的值。

有了 a 的值，就可以轻松得到 b 的值：b = xor ^ a 。

那么下一个问题是，选取哪一位为 1 呢？既然任意一位 1 都可以把 a，b 区分开来，参考上一节，不妨就选择最后一位 1 。

完整算法如下：

public class Q260_SingleNumberIII {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 1, 3, 2, 5};
        System.out.println(Arrays.toString(twoSingleNumbers(arr)));
    }

    static int[] twoSingleNumbers(int[] arr) {
        // 假设两个只出现一次的数为 a，b
        int xor = 0;
        for (int ele : arr) {
            xor = xor ^ ele;
        }
        // 此时 xor = a ^ b
        // 因为 a ≠ b，因此 xor ≠ 0，其二进制必然至少有一个 1
        // 假设 a 在第 N 位为 1
        int rightestBitOne = getRightestOne(xor);
        int elementA = 0;
        for (int ele : arr) {
            if ((ele & rightestBitOne) != 0) {
                // 过滤出含有 a 的元素
                elementA = elementA ^ ele;
            }
        }
        int elementB = xor ^ elementA;
        return new int[]{elementA, elementB};
    }

    static int getRightestOne(int N) {
        return N & (~N + 1);
    }
}

位运算的常用技巧

提取最右侧的 1

int getRightestOne(int N) {
    return N & (~N + 1);
}

抹掉最右侧的 1

int removeRightestOne(int N) {
    return (N - 1) & N;
}

计算二进制中 1 的个数

剑指 Offer 15

int brutalCount(int N) {
    int count = 0;
    while (N != 0) {
        if ((N & 1) != 0) {
            count ++;
        }
        // 考虑负数符号位，最终变成 0xFFFFFFFF 而死循环
        N = N >> 1;
    }
    return count;
}

// Brian Kernighan 算法，跳过连续多个 0
int countWithAnd(int N) {
    int count = 0;
    while (N != 0) {
        count ++;
        // 抹掉最右侧的 1 及后续位置
        N = N & (N - 1);
    }
    return count;
}

int countWithXor(int N) {
    int count = 0;
    while (N != 0) {
        int rightOne = N & (~N + 1);
        count ++;
        // 抹掉最右侧的 1
        // 不可 N = N - rightOne，考虑负数
        N = N ^ rightOne;
    }
    return count;
}

变题 1

判断一个整数是不是 2 的整数次方。

public boolean isTwoToNthPower(int N) {
    // 2 的整数次方，其二进制位上应该有且仅有位是 1
    // 抹掉最后一位 1，该数为 0
    // 负数的符号位？一定大于等于 1 (2^0)
    return (N >= 1) && (((N - 1) & N) == 0);
}

变题 2

输入两个整数 M, N，计算需要改变 M 的几个二进制位才能得到 N 。如 10 = 1010, 13 = 1101，需要改变 3 位。

    public int changeBitCount(int M, int N) {
        // 不同的二进制位 首先想到就是求异或
        // 然后统计异或结果的二进制位中，有多少个 1
        int xor = M ^ N;
        // 一负一正的话，符号位的改变也是要算的上，因此不需要特殊处理
        int count = 0;
        while (N != 0) {
            count ++;
            N = N & (N - 1);
        }
        return count;
    }