位运算

总结下位运算的相关内容

1. 并 A|B
2. 交 A&B
3. 减法 A&~B(即是求解A中不包括B的部分)
4. 求反 ~A
5. 设置某一位为1 A |= 1 << n
6. 清除其他位为0：A &= ~(1 << n)
7. 测试第n位是否为0：A &(1 << n) == 0
8. 抽取最后一位 A & -A or A&~(A-1)
9. 移除最后一位 A&(A-1) 示例：

10. 统计给定数有多少位

    int count(n):
        count = 0
        while n:
            n = n & (n - 1)
            count += 1
        return  count

11. 判断某个数是否是4的指数

def is_power_four(n):
    return !(n & (n - 1)) and (n & 0x55555555)
    # 第一个是判断只有一位有效，第二个是判断是否在正确的位置

^的使用trick

使用^删除完全相同的数字并保存奇数，或保存不同的位并删除它们。

3. 求解两个数的和

def get_sum(a, b):
    return a if b == 0 else get_sum(a ^ b, (a & b) << 1)

使用|的使用trick

可以保留尽量多的1位

翻转数字的位

def  reverse(n):
    mask = 1 << 31
    res = 0
    for i in range(32):
        if n >> i & 1 == 1:
            res |= (mask >> i)
    return res

&的tirck

可以用来选择特定的位
求解一位unsigned int有多少位是1

def hammingweight(n):
    count = 0
    while n:
        n &= (n - 1)
        count += 1
    return count