参考：从集合论到位运算，常见位运算技巧分类总结！ - 力扣（LeetCode） (opens new window)

集合与集合

术语	位运算	举例	举例
交	&
并	|
对称差	^	{0,2,3}^{0,1,2}={1,3}	1101^0111=1010
差	&~	{0,2,3}\{1,2}={0,3}	1101&(~0110)=1001
差(子集)	^	{0,2,3}\{0,2}={3}	1101^0101=1000

集合与元素

术语	位运算	举例	举例
单元素集合	<<	{2}	1<<2
全集	(1<<n)-1	{0,1,2,3}	(1<<4)-1
补集	~
属于	(s>>i)&1=1	2∈{0,2,3}	(1101>>2)&1=1
不属于	(s>>i)&1=0
删除元素	s&~(1<<i)	{0,2,3}\{2}	1101&~(1<<2)
删除元素(在集合中)	s^(1<<i)	{0,2,3}\{2}	1101^(1<<2)
删除最小元素	s&(s-1)
添加元素	s|(1<<i)	{0,3}∪{2}	1001|(1<<2)

函数库

集合大小： Integer.bitCount(s)；

二进制长度(-1得到集合最大元素)： 32-Integer.numberOfLeadingZeros(s)；

集合中最小元素： Integer.numberOfTrailingZeros(s)；

lowbit获取二进制最低1及后面0： s & -s；

集合遍历

遍历0~n-1每个元素，判断元素是否在集合s中

for(int i=0;i<n;i++){
    if(((s>>i)&1) == 1){
        //处理i的逻辑
    }
}

集合枚举

空集枚举到全集

for(int s=0;s<(1<<n);s++){
    //处理s逻辑
}

从大到小，枚举s的所有非空子集

for(int sub=s;sub>0;sub=(sub-1)&s){
    //处理sub逻辑
}

其它

判断奇偶：(x&1)== 0 偶 ，(x&1)==1 奇

交换：

a = a^b;
b = a^b;
a = a^b;

判断1的个数:

int cnt = 0;
while(x!=0){
    cnt++;
    x = x&(x-1);
}

判断2的幂:

boolean ans = x>0 && (x&(x-1)) == 0;