巧妙的位运算

技巧一

x & (x-1) //用于消去x二进制数中最后一个是1的位
x = 1100;
x-1 = 1011;
x & (x-1) = 1000;

应用一

用O(1)时间复杂度检测整数n是否是2的幂次
思路解析：n如果是2的幂次，则n满足两个条件

1. n > 0
2. n的二进制表示中只有最高位有一个1，所以使用n & (n-1)将唯一的一个1消去，应该返回0

练习在LintCode

应用二

计算在一个32位的整数的二进制表达式中有多少个1
思路解析：由x&x(x-1)消去表达式中最后一个1可得，不断的使用x&(x-1)消去最后一个1，直至等于0，计算总共消去多少个1

练习在LintCode

应用三

如果要将整数A转换成B，需要改变多少个bit位？
这个应用是上面一个应用的拓展。
思考将整数A转换为B，如果A和B在第i位相同，则不需要改变这个位，如果在第i位上不相同，则需要改变这个位，所以问题转换成A和B有多少个bit位不同，就可以使用异或运算，相同为0，不同为1，计算A异或B后这个数中1的个数。

练习在LintCode

技巧二

a ^ b ^ b = a

应用一

数组中，只有一个数出现一次，剩下的数都出现两次，求出出现一次的数
思路解析：因为只有一个数恰好出现一次，剩下的都出现过两次，所以只要将所有的数据全部异或起来，就可以得到唯一的那个数。

练习在LintCode

应用二

数组中只有两个数出现一次，剩下的都出现两次，找出出现一次的数
思路解析：有了第一题的基本的思路，我们可以将数组分成两部分，每部分中只有一个元素出现一次，其余元素都出现两次，使用这种方法就可以分别找出两个元素
不妨假设出现一次的两个元素分别是x,y，那么最后所有元素的异或的结果是x^y，并且x^y!=0，那么我们可以找出x^y中某一位1，对于原来的数组就可以根据这一位是不是1，分成两部分，x,y分别在不同的数组中，就可以根据应用一的方法分别找出x,y