二进制集合操作

参考

• oi wiki

基础

一个整数的二进制可以看作是一个集合（0表示在，1表示不在），但是该集合中元素的数目有限

n-1

一个数n，n-1表示：将最低位1删除，且后续的所有0变为1

快速判断一个数是否为2的非负整数幂

bool isPowerOfTwo(int n){return n > 0 && ((n-1)&n) == 0;}

子集遍历

// 降序遍历 m 的非空子集
for (int s = m; s; s = (s - 1) & m) // s 是 m 的一个非空子集

// 降序遍历 n 的子集，处理等于0的子掩码
for (int m = n; ; m = (m - 1) & n)
{ 
	// m 是 n 的一个子集 
	if (m == 0) break; 
}

在掩码中减去1，等价于删除掩码m中的最后一位1，并将之后的所有0变为1。为了使m-1变为新的掩码，需要删除掩码中的额外的1，可以使用位运算(m-1)&n进行
特殊情况是m==0，在执行m-1后变为-1，其所有位均为1，因此会无限循环