leetcode算法-位运算

位运算，直接在二进制上进行的按位操作，位运算的种类如下：

1.按位异或^:异或的含义是操作的两位不同，则结果为1，相同则结果为0，所以两个相同的数异或，结果应该是0，3^3的结果是0,3^4的结果是7（011^100=111），可以看出来异或就是无进位加法啊。异或运算还满足交换律和结合律。a^b^a=b这个其实是因为a^a=0,0^b=b

2.按位与&,操作的两位必须都为1时，结果才为1,1&1=1,1&0=0&1=0&0=0。可以看出来，两个相同的数&运算，得到的还是它自己。两个不同的数计算，得到的是他们相同的位，即取交集

3.按位或|，操作的两位数任意一个为1时，结果就为1,1|1=1|0=0|1=1,0|0=0。可以看出来，两个相同的数|运算，得到的还是它自己，相同不同的数据计算，得到的是他们的并集。

4.按位取反~，这个运算符只有一个操作数，作用就是翻转二进制，如果是有符号的，正负也会随着对调。

5.算数左移<<和算数右移>>，A<<b，将A向左移动b位，空出来的部分补0，右移也是相同的。所以箭头方向就是移动的方向。算数右移可以用来取最小的一位 A&1,A>>1。

典型题目：

461--求汉明距离(二进制不同的位数),先进行异或运算，然后不断的算数右移取最后一位，计算最后一位是1的次数。

190--翻转二进制，把一个10进制的整数按位翻转，按位取反是不行的，因为符号位也会被翻转？

A&1=0 则B<<1 b&1，A&1=1则B<<1,因为算数左移多出来的都是0，所以直接B<<1,B+=A&1即可。

136题，求一个数组内只出现一次的数字，这个解法太巧妙了。x^0=x,x^x=0，而且异或操作是有结合律的，所以异或的顺序并不重要。把所有的数字异或完了，最后还是会剩下单独出现的那一个。