比如给定数组A = [a0, a1, a2, a3, a4]。为了表示从数组A中选择任意个元素的组合状态。组合总和为2的n次方。可以通过位运算达成。 设 bits = 1 << len(A).用bits中的每i位来代表A[i]是否已选。bits的每一个不同的值代表了一种组合。
这个在求线性列表的组合数里面非常有用。也可以用bits来表示具体的选择状态。参见leetcode 698. 划分为k个相等的子集 官方题解的动态规划算法。就是用到了bits来表达选择状态。
x & (x - 1)
x | (x+1)
即-n操作 ~n + 1
lowbit操作取最后一位1及后面的0的值
lowbit(n) = n & (-n)
若有字母a.则转换a的大小写可用异或运算 即 a = a ^ (1 << 5) 原因是异或运算等价于不进位加法
总体来说，a ^ b 等价于不进位的二进制按位相加的结果。因此有： n ^ n = 0 n ^ 0 = n n ^ 0xF: 将最后四位取反
