判断集合中只出现1次的元素

第一次体会到位运算的魅力是遇见Leetcode上“[136] 只出现一次的数字”：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

如果当成一个模拟题来做这题就失去了存在的意义，但有一种方法初看来会有些让人一头雾水：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for(int i = 0;i < nums.length(); i++){
            result = result ^ nums[i];
        }
        return result;
    }
};

“^”符号在位运算中表示异或，处理二进制中两个数的异或时，相同为0，相异为1。相同的十进制数取异或后得到0，那么只出现一次的数就是最后的结果。

拓展思考

数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了一次。请给出最快的方法找到x。

出现三次的元素就无法使用异或的方法了，不妨看看出现三次的十进制整数的二进制有什么特点：

• 1：0001
• 5：0101
• 1：0001
• 5：0101
• 1：0001
• 5：0101

很容易注意到，如果数组中没有出现一次的元素，数组中所有元素在同一位上“1”的个数必然是3的倍数，如第0位有6个“1”，第2位有3个“1”，新引入的出现一次的元素必然会大批这个平衡，故统计数组所有元素同一位“1”的个数即可判断出仅出现一次的元素。

#include <cstring>

int FindNumber(int a[], int n) {
    int bits[32];
    int i, j;
    memset(bits, 0, 32 * sizeof(int));
    for (i = 0; i < n; i++)
        for (j = 0; j < 32; j++)
            bits[j] += ((a[i] >> j) & 1);  // 计算每个数的二进制位数的个数
            // 取int型变量a的第k位 (k=0,1,2……sizeof(int))，即a>>k&1
    // 如果某位上的结果不能被整除，则肯定目标数字在这一位上为
    int result = 0;
    for (j = 0; j < 32; j++)
        if (bits[j] % 3 != 0)
            result += (1 << j);
    return result;
}

在今后遇见的所有元素出现N（N>=3）次的数组中找只出现一次的问题均可采用类似方法。

实际上，位运算不仅性能表现更优，在处理以下问题时还能使代码更加优雅。

判断奇偶

• a&1 = 0 偶数
• a&1 = 1 奇数
  由于十进制数“1”的二进制“0000....0001”只有末位是1，与偶数按位与后为0，与奇数按位与后为1。

对整形变量的第k位进行操作

• 取int型变量a的第k位 (k=0,1,2……sizeof(int))，即a>>k&1
• 将int型变量a的第k位清0，即a=a&~(1<<k)
• 将int型变量a的第k位置1，即a=a|(1<<k)

整数的平均

对于两个整数x,y，如果用 (x+y)/2 求平均值，会产生溢出，因为 x+y 可能会大于INT_MAX，但是我们知道它们的平均值是肯定不会溢出的，我们用如下算法：

int average(int x, int y)   //返回X,Y 的平均值
{   
     return (x&y)+((x^y)>>1);
}

判断一个整数是不是2的幂

对于一个数 x >= 0，判断他是不是2的幂。

boolean power2(int x)
{
    return ((x&(x-1))==0)&&(x!=0)；
}