【总结】位运算常见技巧

原文地址：https://juejin.cn/post/6844903645171941384

判断数的奇偶性

根据数的二进制表示可知，除了最低位的 0 或者 1，其余位都是 0*2^n 或者 1*2^n，必为偶数，偶数 + 偶数 = 偶数，所以决定一个数是否为偶数的关键条件就是二进制最低位是 0 还是 1，如果是 0，则为偶数，否则为奇数（偶数 + 奇数 = 奇数）。此时问题被转化为判断数的二进制表示中，判断最低位是 0 还是 1，这时通过按位与 0x1，过滤掉除去最低位的其他位信息，输出的结果与 0 比较即可判断奇偶性

def is_odd(num):
     # 常见写法
     # return num % 2 != 0
     
    # 使用位运算
    # 根据数的二进制表示可知，除了最低位的 0 或者 1，其余位都是 0\*2^n 或者 1\*2^n，必为偶数，偶数 + 偶数 = 偶数，所以决定一个数是否为偶数的关键条件就是二进制最低位是 0 还是 1，如果是 0，则为偶数，否则为奇数（偶数 + 奇数 = 奇数）。此时问题被转化为判断数的二进制表示中，判断最低位是 0 还是 1，这时通过按位与 0x1，过滤掉除去最低位的其他位信息，输出的结果与 0 比较即可判断奇偶性。
    return num & 1 != 0

判断数是否为 2 的整数次幂

根据数的二进制与十进制的转化规则可知，每一位 bit 乘以 2 的幂次位数和即为十进制表达式，如果一个数为 2 的整数次幂，则此数的二进制中，只能由一位是1，其余位都为0（如果有多个1，则幂次不为整数），所以问题进一步转化为判断一个数的二进制表示中，是否只有一位是 1。这里还需要利用一个性质，即 x & (x - 1) == 0 的充要条件是 x 二进制表达式中只有1个位1，例如 0x00100 & 0x00011 = 0，0x00101 & 0x00100 != 0

def is_log2(num):
    # 使用位运算
    # 根据数的二进制与十进制的转化规则可知，每一位 bit 乘以 2 的幂次位数和即为十进制表达式，如果一个数为 2 的整数次幂，则此数的二进制中，只能由一位是1，其余位都为0（如果有多个1，则幂次不为整数），所以问题进一步转化为判断一个数的二进制表示中，是否只有一位是 1。这里还需要利用一个性质，即 x & (x - 1)  == 0 的充要条件是 x 二进制表达式中只有1个1，例如 0x00100 & 0x00011 = 0，0x00101 & 0x00100 != 0
    return num & (num - 1) == 0

判断数二进制表达中位1的个数

考虑前一个问题：“判断数是否为 2 的整数次幂”，是否可以理解为：“判断数二进制表达中位1的个数是否为1个”，解决方法是通过 num & (num - 1) == 0。那么如何确认二进制表达中是否拥有两个位1呢，我们观察：0x00101 & 0x00100 = 0x00100，再进行一次 0x00100 & 0x00011 = 0，我们发现只需要将 num & (num - 1) 进行两次，最后等于0即可。解决也是如此，每进行一次 num & (num - 1)，都会让最低的那个位1被消除。只需要循环进行操作，记录下次数即可

def cn_1(num):
    # 使用位运算
    count = 0
    while num != 0:
        num = num & (num - 1)
        count += 1
    return count

找出一个数仅出现一次其他数出现两次的数组中的那个数

使用位运算进行处理的前提需要了解并运用一下的异或结论：

任何整数 n 与 0 异或总等于其本身 n，一个数与其本身异或那么结果肯定是 0。即 A ^ A = 0，A ^ 0 = A

同时需要知道，异或满足交换律和结合律:A ^ C ^ A ^ C ^ B == (A^A) ^ (C^C) ^ B

综上：A ^ C ^ A ^ C ^ B = (A^A) ^ (C^C) ^ B = 0 ^ 0 ^ B = B

此题只需要依次对数组的数进行异或，相同的数异或为0，最后的结果则为只出现过一次的值

def find_one(arr):
    # 使用位运算
    e0 = 0
    for item in arr:
        e0 = e0 ^ item
    return e0