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

分析：
由以上可得知，相同数字做^异或运算，会得到0。

代码

def singleNumber(nums):
    num = nums[0]
    for i in nums[1:]:
        num = num ^ i
    return num


# print(singleNumber([1,2,3,4,1,3,2]))
# 4

判断一个数是否是2的幂数，是返回本身，不是返回-1

分析：2的幂数二进制表示：10000....，因此可以位与运算a&(a-1)一定为0

代码

def ispow2(x):
    return x if x&(x-1) == 0 else -1

位运算知识

• 取反(NOT)：使数字1成为0，0成为1。取反操作符用波浪线”~“表示
  ~ 1 0 0 1 1
  -----------------------------
  0 1 1 0 0
  
• 按位或(OR)：两个相应的二进位中只要有一个为1，该位的结果值为1。按位或操作符是”|”
  
  1 0 0 1 1
  | 1 1 0 0 1
  ------------------------------
  1 1 0 1 1
  
• 按位异或(XOR)：两个数如果某位不同则该位为1，否则该位为0。按位异或运算符是”^”
  
  1 0 0 1 1
  ^ 1 1 0 0 1
  -----------------------------
  0 1 0 1 0
• 按位与(AND)：两个相应的二进位都为1，该位的结果值才为1，否则为0。按位与用’&‘表
  
  1 0 0 1 1
  & 1 1 0 0 1
  ------------------------------
  1 0 0 0 1
• 逻辑移位：应用逻辑移位时，移位后空缺的部分全部填0。符号有”>>“和”<<”
  
  • << 左移运算，向左进行移位操作，高位丢弃，低位补 0，如

  int a = 8;
  a << 3;
  移位前：0000 0000 0000 0000 0000 0000 0000 1000
  移位后：0000 0000 0000 0000 0000 0000 0100 0000

  >> 右移运算，向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位，如

  unsigned int a = 8;
  a >> 3;
  移位前：0000 0000 0000 0000 0000 0000 0000 1000
  移位后：0000 0000 0000 0000 0000 0000 0000 0001
  ​
  int a = -8;
  a >> 3;
  移位前：1111 1111 1111 1111 1111 1111 1111 1000
  移位前：1111 1111 1111 1111 1111 1111 1111 1111

  
  

负数在计算机内部的存储方式是补码的形式。负数的补码就等于其正数反码+1。

解题技巧

1.位运算实现乘除法

a = 4
a << 1
# 8
a >> 1
# 2

2.位操作交换两数

a, b = 1,2

#位运算
a ^= b
b ^= a
a ^= b

#引入第三变量
temp = a
a = b
b = temp

#不引人第三变量
a = a+b
b = a-b
a = a-b

#pythonic
a,b = b,a

位与操作解释：第一步：a ^= b ---> a = (a^b);

第二步：b ^= a ---> b = b^(a^b) ---> b = (b^b)^a = a

第三步：a ^= b ---> a = (a^b)^a = (a^a)^b = b

3.位操作判断奇偶数 
只要根据数的最后一位是 0 还是 1 来决定即可，为 0 就是偶数，为 1 就是奇数。

偶数 if 0 == (a&1) else 奇数

4.位操作交换符号
整数取反加1，正好变成其对应的负数(补码表示)；负数取反加一，则变为其原码，即正数

def reversal(a):
    return  ^a +1

5. 位操作求绝对值
整数的绝对值是其本身，负数的绝对值正好可以对其进行取反加一求得，即我们首先判断其符号位（整数右移 31 位得到 0，负数右移 31 位得到 -1,即 0xffffffff），然后根据符号进行相应的操作

def abs(int a) {
  i = a >> 31
    return a^i-i
#  return a if i == 0  else (~a + 1);
}

6. 位操作进行高低位交换

• 给定一个 16 位的无符号整数，将其高 8 位与低 8 位进行交换，求出交换后的值，如：

34520的二进制表示：
10000110 11011000

将其高8位与低8位进行交换，得到一个新的二进制数：
11011000 10000110
其十进制为55430

从上面移位操作我们可以知道，只要将无符号数 a>>8 即可得到其高 8 位移到低 8 位，高位补 0；将 a<<8 即可将 低 8 位移到高 8 位，低 8 位补 0，然后将 a>>8 和 a<<8 进行或操作既可求得交换后的结果。

7. 位操作进行二进制逆序

将无符号数的二进制表示进行逆序，求取逆序后的结果，如

数34520的二进制表示：
10000110 11011000

逆序后则为：
00011011 01100001
它的十进制为7009

在字符串逆序过程中，可以从字符串的首尾开始，依次交换两端的数据。在二进制中使用位的高低位交换会更方便进行处理，这里我们分组进行多步处理。

• 第一步:以每 2 位为一组，组内进行高低位交换

交换前： 10 00 01 10 11 01 10 00
交换后： 01 00 10 01 11 10 01 00

• 第二步：在上面的基础上，以每 4 位为 1 组，组内高低位进行交换

交换前： 0100 1001 1110 0100
交换后： 0001 0110 1011 0001

• 第三步：以每 8 位为一组，组内高低位进行交换

交换前： 00010110 10110001
交换后： 01100001 00011011

• 第四步：以每16位为一组，组内高低位进行交换

交换前： 0110000100011011
交换后： 0001101101100001

对于上面的第一步，依次以 2 位作为一组，再进行组内高低位交换，这样处理起来比较繁琐，下面介绍另外一种方法进行处理。先分别取原数 10000110 11011000 的奇数位和偶数位，将空余位用 0 填充：

原数：  10000110 11011000
奇数位： 10000010 10001000
偶数位： 00000100 01010000

再将奇数位右移一位，偶数位左移一位，此时将两个数据相或即可以达到奇偶位上数据交换的效果：

原数：  10000110 11011000
奇数位右移一位： 0 10000010 1000100
偶数位左移一位：0000100 01010000 0
两数相或得到： 01001001 11100100

上面的方法用位操作可以表示为：

• 取a的奇数位并用 0 进行填充可以表示为：a & 0xAAAA
• 取a的偶数为并用 0 进行填充可以表示为：a & 0x5555 因此，上面的第一步可以表示为：
  a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1)
  同理，可以得到其第二、三和四步为：
  a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2)
  a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4)
  a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8)