二进制枚举以及集合的关系运算

• 一、按位运算符
• • 1.移位运算符
  • 2.逻辑按位运算符
• 二、二进制枚举
• • 1.枚举单一集合的子集
  • • 1.1.1 相关数学概念及性质
    • 1.1.2 集合常用关系
    • 1.1.3 如何枚举所有子集方案

val<>shift //向右移

v a l 是被操作的整数值， s h i f t 是要要移动的数位 color{orange}val是被操作的整数值，shift是要要移动的数位 val是被操作的整数值，shift是要要移动的数位

注 color{Red}注 注

• 腾出的位置用0填充，超出边界的位置被丢弃
• 每一位是前一位的2倍，因此每左移一位相当于乘2，左移n位相当于乘2^n
• C++左移运算符生成一个新值，不修改原来的值

①位非运算符（~），将每一位转化为它的反面（1转化而为0,0转化为1）
②或运算符 OR（|），被操作的两个值得对应位至少有一个1，则新值为1，否则为0
③与运算符 AND（&），被操作的两个值对应位都为1，则新值为1，否则为0
④异或运算符 XOR（^），一个为1，一个为0则新值为1，否则为0

注 color{Red}注 注

• 这里的位均对于二进制数来说的

• 子集：如果集合A的任意一个元素都是集合B的元素，那么集合A称为集合B的子集。

• 子集的个数：含 n 元素的子集的个数为 2 n 2^n 2n

考虑一集合A={1，2，3，4，5}和它的四个子集A1，A2，A3，A4，如以下所示

1. 并集:从元素角度来看，就是A1、A2包含的元素合并起来得到A1。

   即是按位或 ：

   A1= A1|A2

2. 交集：是指两个集合同时存在的元素组成的集合。可以看出 A1、A4的交集得到 A3。

   即是按位与：

   A3=A1&A4

3. 属于：是指某一元素在集合中。只需检查某项元素构成的集合是否是另一集合的子集。

   一般地，可以先用左移运算构造出那个仅含一项的集合，然后再和原集合取交集 , 若不为空集，则命题成立 color{orange}一般地，可以先用左移运算构造出那个仅含一项的集合，然后再和原集合取交集,若不为空集，则命题成立 一般地，可以先用左移运算构造出那个仅含一项的集合，然后再和原集合取交集,若不为空集，则命题成立

   • 判断第 i （1<= i <=n） 个元素是否属于某一集合 Ax
   • 即是 1<<( i-1)&Ax

4. 补集：是指全集去掉某个集合后剩下元素组成的集合。如 A2对于全集的补集就是A3。

   即是：

   A^A2

对于选取一个集合中的元素构成子集，我们设 1 为 选取，0 为不选取

由性质可知对于 n 个元素的子集不超过 2 n 2^n 2n个，于是不断缩小 n 所对应的二进制数就可以列举所有方案。

#include

using namespace std;

int main()
{
    int n;
    
    for(int i=0;i<1<
        for(int j=0;j>j&1)
                cout<<1;
        	else
                cout<<0;
        
        cout< 
 
 

      
       
        
         
          
           注
          
         
        
        
         color{Red}注
        
       
      注
 
 
此种方法只是相对于多重循环来说，更方便，但依然是采用枚举的方式，因此只适用于枚举方案较少的情况