集合与位运算

// 集合论 和 位运算 联系
/*
    Q1：如何表示元素在集合中？
        集合 {0,2,3} 可以压缩成 0b1101
        
        说明集合中的元素连续，如：a~z 可表示为 ch - 'a'
​   
    Q2: 集合与集合：
        交集：A∩B   -   a&b
        并集：A∪B   -   a|b
        对称差: A▲B -   a^b   {0, 2, 3} ▲ {0, 1, 2} = {1 , 3} 
        差： A\B    -   a&(~b)  {0, 1, 2, 3}\{4,3} = {0,1,2}
        差（前提：存在子集关系) 
            A\B, B包含于A  -  a^b
        包含于: A⊆B -   a&b = a 或 a|b = b
*/
 
// 集合与集合注意事项
// 1、取反操作若要获得正确操作，需要&0b111... (1的个数为当前元素个数)
// 2、A包含于B还可以用 a&(~b) == 0 进行判断
// 3、C++中：按位移（>>, <<）大于 == 大于 按位运算符（&, |, ^, ~）
#include<iostream>
#include<bitset>
using namespace std;
void AmongSets(){
    // 1、取反操作
    int U = 0b1001;
 
    // cout << (~U) << endl;  // 错误,输出 -10, 理应输出6
    // 原因：32位二进制表示 11111111111111111111111111110110, int值为-10
    // cout << ~bitset<32>(U) << endl; 
 
    // 正确操作
    cout << ((~U) & 0b1111) << endl;
 
    // 2、判断包含关系
    int S = 0b1000;
 
    cout << (bool)((U | S) == U) << endl;
    cout << (bool)((U & S) == S) << endl;
    cout << (bool)((S & (~U)) == 0) << endl;
}
 
/*
    集合与元素间关系
        1、全集 U -  (1 << n) - 1
        2、补集 CuS = U\S  -  ((1 << n) - 1) ^ s
        3、属于 i∈S -  (s >> i) & 1 == 1
        4、不属于 i不属于S  - (s >> i) & 1 == 0
        5、添加元素  S∪{i} -  s|(1 << i)
        6、删除元素  S\{i} -   s&(~(1<<i))
        7、删除元素（一定在集合中） S\{i}, i∈S
            s^(i<<i)
        8、删除最小元素 s&(s - 1)
            例如：s = 101100
                s-1 = 101011
                s&(s-1) = 101000  
*/
void Element_Set(){
    // S {1,2,4,5,7}
    int S = 0b10110110;
 
    // 计算补集 {0,3,6}
    int Cus = ((1 << 8) - 1) ^ S;
 
    cout << bitset<8>(Cus) << endl;
    // 0b01001001
 
    // 判断{3}是否属于集合S
    cout << (bool)(((S >> 3) & 1) == 1) << endl;
    
    // 添加元素{3}
    S |= (1 << 3);
    cout << bitset<8>(S) << endl;
 
    // 删除元素{6}  - 6本身就不在集合中
    S &= (~(1 << 6));
 
    cout << bitset<8>(S) << endl;
 
    // 删除在集合中的元素 {5}
    S ^= (1 << 5);
 
    cout << bitset<8>(S) << endl;
 
    // 删除最小元素
    cout << bitset<8>(S & (S - 1)) << endl;
}
 
/*
    二进制相关库
        1、集合大小(计算二进制中的 1 的个数)  __builtin_popcount(s)
            【注】 c++的long long, 需要使用__builtin_popcountll()函数
        2、二进制长度 __lg(s) + 1
        3、集合最大元素(减一后得到集合最大元素 - 原因: 从0开始计数)  __lg(s)
            【注】 __lg 支持 long long
        4、 集合最小元素(计算二进制尾零个数)  __builtin_ctz(s)
            【注】 __lg(0) 和 __builtin_ctz(0)都是未定义行为
*/
 
void Hfile_BinarySystem(){
    int U = 0b101011111;
 
    // 集合大小
    cout << __builtin_popcount(U) << endl;
 
    // 二进制长度
    cout << __lg(U) + 1 << endl;
    
    // 集合最大元素
    cout << __lg(U) << endl;
 
    // 集合最小元素
    cout << __builtin_ctz(U) << endl;
}
 
// 一个特殊情况，取只包含最小元素的子集 (lowbit, s&-s)
/*
    s = 101100
    ~s = 010011
    -s = ~s + 1 = 010100 // 补码定义：-s  =>  s 的最低 1 左侧取反，右侧不变
    s & -s = 000100  // lowbit
*/
 
void lowbit(){
    int s = 0b101100;
    
    cout << bitset<6>(s & (-s)) << endl;
}
 
/*
    遍历操作
*/
 
void traverse(){
    int s = 0b101100;
    // 1、枚举元素i，看其是否在集合s中
    for(int i = 0; i < __lg(s) + 1; ++i){
        if((s >> i) & 1)
            cout << "i: " << i << ", is in the set S" << endl;
    }
 
    // 2、遍历集合s中的元素，不断计算集合最小元素，去掉最小元素，直到集合为空
    for(int t = s; t; t &= t - 1){
        int i = __builtin_ctz(t);
        cout << "i: " << i << ", is in the set S" << endl;
    }
}
 
/*
    枚举操作
*/
 
void enumerate(){
    // 1、枚举从空集到全集的所有集合 0... n-1
    for(int i = 0; i < (1 << 4); ++i){
        cout << bitset<4>(i) << endl;
        // 处理集合逻辑
    }
 
    int s = 0b101100;
    // 2、枚举集合S的所有非空子集
    int sub = s;
    while(sub){
        // 处理子集逻辑
        cout << "subset: " << bitset<6>(sub) << endl;
        sub = (sub - 1)&s;
    }
 
    /*
        为什么 sub = (sub - 1)&s 就能跳到下一个子集呢？
        
        例子： s = 101100
        sub = 101100         // 子集1：101100
        sub - 1 = 101011
 
        s&(sub - 1) = 101000  // 子集2：101000
 
        sub - 1 = 100111
        s&(sub - 1) = 100100  // 子集3：100100
 
        sub - 1 = 100011
        s&(sub - 1) = 100000  // 子集4：100001
 
        sub - 1 = 011111
        s&(sub - 1) = 001100  // 子集5: 001100
 
        原因： sub - 1 会将最低位置1变成0，最低位置右边的0变成1，与s取交集，最低位置右侧会取到s的子集
    */
 
    // 枚举 s的所有子集（包括空集）
    sub = s;
    do{
        // 处理子集逻辑
        cout << "subset(contain null): " << bitset<6>(sub) << endl;
        sub = (sub - 1) & s;
    }while(sub != s);
 
    // 原理：当sub = 0 时，减1就得到-1，对应二进制为111...1，再&s就得到了s
}
 
// 一个特殊的枚举情况：枚举全集U中的大小为K的子集 - Gosper's Hack
/*
    例子： 0001111 -> 1111000 (n = 7, k = 4)
    
    Q: 如何进行操作呢？（了解操作即可）
        中间过程
            0110110 ->
            0111001
        左边部分 left = lowbit + x
        右边部分 right = ((lowbit + x) ^ x) // lowbit >> 2
        然后将左右部分拼起来就是当前子集的下一个子集
*/
 
void Gosper_Hack(int n, int k){
    // 开始条件： x = (1 << k) - 1
    // 循环条件： x < (1 << n)
    int x = (1 << k) - 1;
 
    while(x < (1 << n)){
        // 处理U中大小为k的子集的逻辑
        cout << "size of k subset: " << bitset<8>(x) << endl;
        
        // 下一个满足 个数为k的子集
        int lb = x & -x;
        int left = lb + x;
        int right = ((lb + x) ^ x) / lb >> 2;
 
        x = left | right;
    }
}
 
// 枚举超集
/*
    超集： 若T为S的子集，则S为T的超集
    s = (s + 1) | t 
*/ 
void superset(){
    int n = 7;  // 集合中有7个元素
    int t = 0b101001;
    int s = t;
    while(s < (1 << n)){
        // 处理超集逻辑
        cout << "superset of T is: " << bitset<7>(s) << endl;
        s = (s + 1) | t;
    }
}
 
 
 
int main(int arg, char **args){
    // AmongSets();
    // Element_Set();
    // Hfile_BinarySystem();
    // lowbit();
    // traverse();
    // enumerate();
    // Gosper_Hack(9, 5);
    superset();
    return 0;
}

bitset库