位运算

位运算不仅可以简化某些复杂的操作，而且具有更快的计算速度。典型的应用就是除法，交换两个数值，以及在一个数组中寻找只出现一次的数字等待。

常见的位运算：

• 左移<<，右移>>
• 按位与&，按位或|
• 异或^

左移右移

• 判断倒数第i+1位是1还是0

num = num >> i
return num&1

• 整数右移一位等价于整数除以2（取整）

异或运算的特性：

一个数字异或它自己结果为0，异或0结果为它自己即a^a=0，a^0=a，且异或满足a^b^c=a^(b^c)。

例如查找数组[1,2,3,2,1]中只出现1次的数字，其他数字都出现偶次

我们可以设置一个ret异或每个数组元素，最后相同的都抵消为0，那个唯一的数字异或0为它自己即为答案。

ret = 0
for i in nums:
    ret^=i
return ret

# ret = 0^1^2^3^2^1=3

剑指offer40：数组中只出现一次的数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度为O(n)，空间复杂度为O(1)。

解题思路：

• 将数组划分为两个数组，一个数组中包含其中一个出现奇次的数，其他的都是偶数次；另一个数组同理。这样子就可以用上述方法找出两个数组中出现奇次的数
• 那如何将数组划分呢？先全部异或，其余出现两次必定都相消，只留下两个只出现一次的数a ^ b结果，由于ab不同，异或结果不同，这样子二进制肯定里面有1，找到有1的那个位置，说明这个位置a，b二进制位不同，这样子根据这个位就可以将ab分组。 核心就是将ab分组，其他出现两次的数字只要保证两两一组就可以，至于在哪个组无所谓，反正异或完都相消了。

剑指offer 10：二进制中1的个数

例如把9表示成二进制是1001，有2位是1。因此如果输入9，该函数输出2

    def NumberOf1(self, n):
        # write code here
        count = 0
        for i in range(32): # 模拟int是4个字节
            if n & 1 == 1:
                count+=1
            n=n>>1
        return count