算法（12）：位操作

按位操作是真的复杂，且技巧性很高，特此专门开一篇，来简单讲解。

目录：
算法：附录
 算法（1）：递归
 算法（2）：链表
 算法（3）：数组
 算法（4）：字符串
 算法（5）：二叉树
 算法（6）：二叉查找树
 算法（7）：队列和堆栈（附赠BFS和DFS）
算法（8）：动态规划
 算法（9）：哈希表
 算法（10）：排序
 算法（11）：回溯法
 算法（12）：位操作

原码、反码、补码讲解

LeetCode 位操作例题 (C++版本)

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)

暂且完结，撒花~~~