算法（12）：位操作
按位操作是真的复杂，且技巧性很高，特此专门开一篇，来简单讲解。
- 目录：
算法：附录
算法（1）：递归
算法（2）：链表
算法（3）：数组
算法（4）：字符串
算法（5）：二叉树
算法（6）：二叉查找树
算法（7）：队列和堆栈（附赠BFS和DFS）
算法（8）：动态规划
算法（9）：哈希表
算法（10）：排序
算法（11）：回溯法
算法（12）：位操作
1. 原码
原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值. 比如如果是8位二进制:
[+1]原 = 0000 0001
[-1]原 = 1000 0001
第一位是符号位. 因为第一位是符号位, 所以8位二进制数的取值范围就是[-127 , 127]，即:
[1111 1111 , 0111 1111]
2. 反码
反码的表示方法是:
正数的反码是其本身
负数的反码是在其原码的基础上, 符号位不变，其余各个位取反.
[+1] = [00000001]原 = [00000001]反
[-1] = [10000001]原 = [11111110]反
3. 补码
补码的表示方法是:
正数的补码就是其本身
负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)
[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补
计算机储存数据都是用补码的方式储存的，c++里面获取某个数的二进制表示(也就是补码)如下：cout << bitset<sizeof(int) *8> (num) << endl;
例题1： 计算一个数转化为2进制之后，包含多少1。（ 又称之为 Hamming weight，汉明重量）
输入：5
输出：2（0101）
解释：
n = n & (n-1)可以消除二进制位最右边的一个1。
如：0101 & 0100，结果为 0100， 和 0101相比，第四位的1消失了，计数器加1；
再继续0100 & 0011，结果为 0000， 和0100相比，第二位的1消失了，计数器加1；
此时n=0，跳出循环。
def solution(n):
count = 0
while n:
n = n & (n-1)
count += 1
return count
ans = solution(15)
print(ans)
例题2：判断一个数是否为2的指数幂。
输入：8
输出：True
解释：
1的二进制为1
2的二进制为10
4的二进制为100
8的二进制为1000
发现只有最高位为1其余位为0，如果将其减一的话那么最高位为0其余位则为1，两者相与的结果则必定为0
结论：如果 a&(a-1) == 0 则a必定是2的指数幂
def solution(n):
return (n & (n - 1)) == 0
ans = solution(16)
print(ans)
例题3：判断一个数是否为4的指数幂。
输入：16
输出：True
解释：
1的二进制为1
4的二进制为100
16的二进制为10000
第一句不多说，(num & (num - 1)) == 0用来判断是不是2的指数幂，第二句则是去除掉是2的指数幂，但不是4的指数幂的部分。
def solution(num):
return (num & (num - 1)) == 0 and (num - 1) % 3 == 0
#或者下面这种写法也行
# return (n&(n-1)) == 0 and n & 0x55555555
ans = solution(16)
print(ans)
例题4：两整数求和。
输入：-1，1
输出：0
解释：
下面代码中 a 储存不包含进位的计算结果，即(a ^ b)；
b 只储存进位的结果，即(a & b) << 1)；
当b等于0时，代表没有进位，跳出循环。
至于mask的作用，因为理论上 python 里 int 类型的位数是没有上限的，不同与c++，int为32位。而最后一句的~(a ^ mask)，其实在二进制位上，执行前后是的结果是一样的，但表达含义变化了，将第一位变为了符号位。
如 4294967276（大于2的31次方），其二进制表示为：
...11111111111111111111111111101100（...表示前面还有很多位，因为 int 类型的位数是没有上限），
a ^ mask得：
00000000000000000000000000010011（此时前面的都mask掉了，第一位为符号位，该数为19）
再^求反得：
11111111111111111111111111101100（和4294967276的二进制完全相同，但是含义变成了-20）
class Solution:
def getSum(self, a, b):
"""
:type a: int
:type b: int
:rtype: int
"""
# 32 bits integer max
MAX = 0x7FFFFFFF
# 32 bits interger min
MIN = 0x80000000
# mask to get last 32 bits
mask = 0xFFFFFFFF
while b != 0:
# ^ get different bits and & gets double 1s, << moves carry
a, b = (a ^ b) & mask, ((a & b) << 1) & mask
# if a is negative, get a's 32 bits complement positive first
# then get 32-bit positive's Python complement negative
return a if a <= MAX else ~(a ^ mask)
例题5：缺失的数字
给一个长度为n的数组，里面存放从0到n的数，但是少了一个，求出该数。
输入：[0，1，2，4，5]
输出：3
解释：对0和某一个数进行异或操作，则结果为该数；
某个数对另一个数进行两次 ^异或操作，则结果还是该数本身。
def solution(arr):
ans = 0
for i,num in enumerate(arr):
ans ^= num
ans ^= i
return ans^len(arr)
ans = solution([0,1,2,4,5])
print(ans)
例题6：将一个32位无符号整数，进行按位翻转
输入：12
输出：805306368
解释：
00000000000000000000000000001100 （12的32进制表示）
00110000000000000000000000000000 （805306368的32进制表示）
def solution(n):
ans = 0
mask = 1<<31
while n:
if n&1:
ans |= mask
mask >>= 1
n>>= 1
return ans
n = 12
print(bin(n)[2:].zfill(32))
ans = solution(n)
print(bin(ans)[2:].zfill(32))
例题7：逐个元素进行and 操作。给出一个区间[m, n]，且 0 <= m <= n <= 2147483647，对m到n之间的每个元素进行与操作，返回操作的结果。
输入：[5,7]
输出：4 （101 &110 & 111）
解释：将5和7一直左移，并不断判断左移后两个数是否相等，如果相等（此时已经左移两次，1==1），则跳出循环，然后右移相同位数（两位），并返回结果，即4。
def solution(m,n):
a = 0
while m!=n:
m>>=1
n>>=1
a += 1
return m<<a
ans = solution(5,7)
print(ans)
多运算符混合应用题目
例题8： DNA重复序列。某DNA序列由ACGT四个字母组成，需要找出里面所有长度为10，且出现重复的序列。
输入：'AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT'
输出：['AAAAACCCCC', 'CCCCCAAAAA']
输入：’AAAAAAAAAAA'
输出：['AAAAAAAAAA']
附注：注意里面的运算优先级，首先 +/-优先级最大，其次<< ， 随后是 &，| 的优先级最小。
def solution(s):
d = {}
ans = []
num = 0
if len(s)<11: return []
for i in range(9):
num = num<<3 | ord(s[i]) - ord('A')+1 & 7
# 上面相当于 num = (num<<3) | ((ord(s[i]) - ord('A')+1) & 7)
for i in range(9,len(s)):
num = num << 3 & 0x3fffffff | (ord(s[i]) - ord('A')+1) & 7
if d.get(num) == 1:
ans.append(s[i-9:i+1])
d[num]=d.get(num,0)+1
return ans
ans = solution('AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT')
print(ans)
例题9：单独数字。给出一个数组，该数组中有两个元素只出现一次，其他的都出现两次，请找出这两个元素。
输入：[1,1,2,2,3,4]
输出：[3,4]
解释：第一步，对所有元素进行异或操作，某一位出现1的次数为奇数次，才会为1；
第二步，bit = bit & ~(bit - 1)，找出最右边第一位为1的二进制位，其余全置零。
（eg：bit = 101100，执行完之后，bit = 000100）；
第三步，再次遍历数组，通过该比特位将数据分为两部分，这两部分各包含一个只出现一次的元素，以及若干个成对出现的元素。
def solution(arr):
bit = 0
for i in arr:
bit ^=i
bit = bit & ~(bit - 1)
ans =[0,0]
for i in arr:
if bit & i:
ans[0]^=i
else:
ans[1]^=i
return ans
ans = solution([1,2,3,5,1,3])
print(ans)
例题10：单独数字。给一个数组，其中只有一个元素出现一次，其他都出现了三次，找出该元素。
输入：[1,1,1,3,4,4,4]
输出：3
解释：（此题解法通用性很强，题目可以改成：一个元素出现m次，其他元素都出现了k次，只要m不为k的整数倍即可用该题方法来求解。）
def solution(arr):
barr = [0] * 32
for n in arr:
for i in range(0, 32):
if n & (1 << i):
barr[i] = (barr[i] + 1) % 3
ans = 0
for i in range(0, 32):
ans = ans | barr[i] << i
return ans if ans <= 0x7fffffff else ~(ans ^ 0xffffffff)
ans = solution([1,1,1,-3])
print(ans)
例题11：单词长度的乘积。给定一个包含各种单词的数组，返回一个最大值，该最大值为：两个不含相同字符的单词，其长度的乘积最大值（即len(word[i]) * len(word[j])） 。
输入：["a","ab","abc","d","cd","bcd","abcd"]
输出：4 （ len('ab') * len('cd') = 4）
输入: ["a","aa","aaa","aaaa"]
输出: 0 （找不到满足条件的一对单词）
def maxProduct(words) :
mask = [0] * len(words)
ans = 0
for i in range(len(words)):
for c in words[i]:
mask[i] |= 1 << ord(c) - ord('a')
for j in range(i):
if not mask[i] & mask[j]:
ans = max(ans, len(words[i]) * len(words[j]))
return ans
ans = maxProduct(["abcw","baz","foo","bar","xtfn","abcdef"])
print(ans)
例题12： 求一个集合所有子集。(这应该是最后一题了，，，)
输入：[2,3,5]
输出：[[], [2], [3], [2, 3], [5], [2, 5], [3, 5], [2, 3, 5]]
解释：
对于集合当中每个数字，都有要、不要两种选择，所以子集个数为 2的len(arr)次方 （即下面的 size）。
注意下面的关键句if (1 << j & i)，该句子可以实现如下取舍方式：
对于第一个数，1 << j = 1, 二进制为0001，与 i 进行按位与操作后，其取舍方式为：
0，1，0，1，0，1，0，1...
对于第二个数，1 << j = 2, 二进制为0010，与 i 进行按位与操作后，其取舍方式为：
0，0，1，1，0，0，1，1...
对于第三个数，1 << j = 4, 二进制为0100，与 i 进行按位与操作后，其取舍方式为：
0，0，0，0，1，1，1，1...
def solution(arr):
size = 1 << len(arr)
print(size)
ans = [[] for i in range(size)]
for i in range(len(ans)):
for j in range(len(arr)):
if (1 << j & i):
ans[i].append(arr[j])
return ans
ans = solution([2,3,5])
print(ans)
暂且完结，撒花~~~
