位运算问题

1. 只出现一次的数字 III

题目描述：

算法原理：
因为两个相同的数经过异或就等于0，所以首先将数组中的每个数字异或到一起，这样就得到了两个出现一次的元素的异或值。假设得到的异或值为n，那么我们去求异或值的最低位的1，也就是将n&（-n）,通过这个最低位的1就可以将nums数组分为两类，一类是在这一位为0，一类是在这一位为1，将这两类数分别一起异或即可分别得到两个只出现一次得元素。
代码如下：

class Solution {
    public int[] singleNumber(int[] nums) {
        int sum = 0;

        for (int x : nums) {
            sum ^= x;
        }

        sum = (sum == Integer.MIN_VALUE ? Integer.MIN_VALUE : (sum & -sum));

        int[] arr = new int[2];
        for (int x : nums) {
            if ((sum & x) != sum) {
                arr[0] ^= x;
            } else {
                arr[1] ^= x;
            }
        }

        return arr;
    }
}

题目链接

2. 丢失的数字（268）

题目描述：

算法原理：
这题比较简单有很多方法，这里就介绍以下位运算的解法，题目给了n长度的数组，数组中填写0到n数字中的任意n-1个数字，然后叫我们去找没有放到数组中的值，实际上很简单就直接将0到n的数字以及数组中的数字一起异或即可得到最终结果。
代码如下：

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int ret = 0;
        for (int i = 0; i < n; i++) {
            ret ^= i;
            ret ^= nums[i];
        }

        return ret ^ n;
    }
}

题目链接

3. 两整数之和（371）

题目描述：

算法原理：
异或有一个特性就是相加但是不进位，所以我们首先将a和b相异或得到mul。之后我们处理进位，将a和b相与得到carry只有同一位都为一时最终的结果carry中的同一位才会为1，但是此时的进位距离真正的进位还需要整体向左移动一位，这还是比较好理解的。最终将移动后的carry和mul分别作为新的b和a重复上述的过程直至b等于0也就是进位等于0的时候停止。之后返回a也就是两数之和。
代码如下：

class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            int mul = a ^ b;
            a = mul;
            b = carry;
        }
        return a;
    }
}

题目链接

4. 只出现一次的数字 II（137）

题目描述：

算法原理：
因为其它数字都是重复出现了三次，假设将所有的数字按位累加起来，我们先对任意一位进行分析，假设单独出现一次的数字一位为0时，在按位累加之和就会出现两种情况，第一种就是0，第二种就是3n，当单独出现一次的数字的一位为1时也会出现两种情况，第一种就是1，第二种就是3n+1（上述的n可能会小于数组总的长度），当我们将上述的四种情况的结果%3的时候不难发现最终得到的数字就是单独出现一次的数字的在那一位的数字，这样我们就可以将每一位都这样相加最终%3得到单独出现的数字的每一位进而得到单独出现的那一个数字。
代码如下：

class Solution {
    public int singleNumber(int[] nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (int j = 0; j < nums.length; j++) {
                if (((nums[j] >> i) & 1) == 1) {
                    sum++;
                }
            }
            sum %= 3;
            ret |= (sum << i);
        }

        return ret;
    }
}

题目链接

5. 消失的两个数字（面试题 17.19.）

题目描述：

算法原理：
这题是第一题和第二题的糅合，首先通过第二题的思想将数组中所有值和1到N（N就是nums.length+2）中所有值异或到一起得到消失的两个数字的异或值sum，再通过第一题的思想将sum&(-sum)得到sum最右端的1并且将其它位变为0，之后在nums数字以及1到N中去遍历，当遍历的值&sum等于sum的值分为一类，不等于另外分为一类并且分别异或放到数组中返回。
代码如下：

class Solution {
    public int[] missingTwo(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum ^= nums[i];
            sum ^= i + 1;
        }
        sum ^= nums.length + 1;
        sum ^= nums.length + 2;

        int temp = sum & (-sum);
        int[] ret = new int[2];
        for (int i = 1; i <= nums.length + 2; i++) {
            if ((temp & i) != temp) {
                ret[0] ^= i;
            } else {
                ret[1] ^= i;
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if ((temp & nums[i]) != temp) {
                ret[0] ^= nums[i];
            } else {
                ret[1] ^= nums[i];
            }
        }
        return ret;
    }
}

题目链接