Bit manipulation

黑魔法，没多说的，下面的小技巧全背下来就行

• 消去整数二进制最低位的1：x & (x - 1)
• 求整数二进制最低位的1：x & ~(x - 1) 或者 x & -x
• check parity(整数二进制数1的个数是奇还是偶

"""
时间复杂度为O（k），k为数字本身1的个数
"""

def parity(x):
    result = 0
    while x:
        result ^= 1
        x &= x - 1              # 舍弃最低位的1
    return result

"""
时间复杂度为O（lgn），我也没懂为啥
"""

def parity2(x):
    x ^= x >> 32
    x ^= x >> 16
    x ^= x >> 8
    x ^= x >> 4
    x ^= x >> 2
    x ^= x >> 1
    return x & 0x1

• 比特位交换，O（1）复杂度

def swap_bits(x, i, j):
    """
    交换x的二进制上第i位和第j位的值
    """
    if (x >> i) & 1 != (x >> j) & 1:
        bit_mask = (1 << j) | (1 << i)
        x ^= bit_mask
    return x

这里提一下，有些字符串类型相关的题目也会跟Bit位操作扯上关系，为什么呢？原因就是英文26个字母如果只通过bitmap的方式来保存的话也不可能大于一般电脑32位机的整型数范围，所以这里就可以通过一个bitmap甚至是一个单独的整数来表示这些字母的存在与否，大大节省了查找时间