优化 bool 数组空间

王熙文 · 2021-05-05 15:21:46 · 算法·理论

upd on 2022.11.18: 其实就是手写 bitset。

注：

本文内容均自创。
文中代码为 C++，但思路使用哪种语言都可以写出。
欢迎指出错误、优化代码（我正求之不得呢）。

感谢 @SAMSHAWCRAFT 大佬指出错误！（我把 (B[wz]+=(1<<add),++cnt) 写成了 (B[wz]+=(1<<add,++cnt))）

感谢 @Quick_Kk 大佬指出 change 的 “想改为 0 并且二进制位置上的数为 0，将这个数加上 2^add。” 应改为 “想改为 1 并且二进制位置上的数为 0，将这个数加上 2^add。”

Part 1 思路 & 代码：

1. 存储方式：

我们知道，二进制数的每一位，是 0/1，那么二进制数就可以存储一段区间内每一个位置的 bool 值（true/false）。

那么二进制数如何存储呢？可以把二进制数化成十进制数，放到某个数据类型里。

我们又知，unsigned int 的最大值是 2^{32}-1，化为二进制数是 111..11（32 个 1），这样，每一个 unsigned int 数都可以表示 32 个 bool 值。

这里，我们就采用 unsigned int 这个数据类型来存 bool 值。

那么数组的大小开多少呢？因为我们一个数可以原数组表示 32 个，所以大小只用开到原数组的 \large\frac{1}{32} 就行了。

这一段代码：

unsigned int B[(100000000+10)/32]; // 100000000 是原来的空间

2. 改变某位置的数：

注：位置为原位置，不是数组的位置。

设原位置为 \textrm{wz}。我们需要先求出这个位置所在 unsigned int 数组的位置，很明显，这个位置是 \large \frac{\textrm{wz}}{32}，定义 \textrm{wz1} 为这个数。

我们还需求出这个位置在数组的数化成二进制后的位置（从右往左第几个，最右边的那个是第 0 个），这个位置是 \textrm{wz} \bmod 32，定义 \textrm{add} 为这个数。

那么如何求出该位置上的布尔值是 true 还是 false 呢？想象一下我们刚开始学编程的时候，有一道题是让你求出一个数的十位是多少。这题很简单对吧，代码：x/10%10。如果让你求出百位呢，代码：x/100%10。其实现在这个问题就是这道题变成了二进制，想求出的十位百位就是 \textrm{add}。（代码一会儿揭晓）

现在分类讨论：

想改为 0 并且二进制位置上的数为 1，将这个数减去 2^{\textrm{add}}。（可以想一下二进制转十进制时每个为 1 的位置产生的价值）。
想改为 0 并且二进制位置上的数为 0，不用改。
想改为 1 并且二进制位置上的数为 1，不用改。
想改为 1 并且二进制位置上的数为 0，将这个数加上 2^{\textrm{add}}。

这一段代码：

void change(int wz,int turn) {
    int wz1=wz/32,add=wz%32;
    if(turn==0 && B[wz1]/(int)pow(2,add)%2==1) {
        B[wz1]-=pow(2,add);
    }
    if(turn==1 && B[wz1]/(int)pow(2,add)%2==0) {
        B[wz1]+=pow(2,add);
    }
}

3. 查询某位置的数：

其实上文已经提到了如何查询，就是 if 判断的第二个表达式，这里给出代码：

bool find(int wz) {
    return B[wz/32]/(int)pow(2,wz%32)%2;
}

4. 清空：

所有数都变成 false：其实相当于 unsigned int 数组里的所有数都变成 0。这很耗时间，memset 一下就行了。
所有数都变成 true：相当于 unsigned int 数组里的所有数都变成二进制的 111..11（32 个 1）的十进制数。这个数是：0xFFFFFFFF。也 memset 一下就行了，在 memset 里也可以写成 0xff。

代码：

void allReset(int turn) {
    if(turn==0) {
        memset(B,0,sizeof(B));
    }
    if(turn==1) {
        memset(B,0xff,sizeof(B));
    }
}

5. 总代码：

这个代码包含了 int main() 里的测试，当做不存在就行了。

#include<bits/stdc++.h>
using namespace std;

// bool 数组优化空间 

// 一个正整数（unsigned int）化成 2 进制数也可以表示 true/false

unsigned int B[(100000000+10)/32]; // 100000000 是原始空间 

// unsigned 的最大值是 2^32-1，相当于二进制的 111...11（32 个 1），所以每个 unsigned 都是 32 个 bool 

// 改变代码： 

void change(int wz,int turn) {
    int wz1=wz/32,add=wz%32;
    if(turn==0 && B[wz1]/(int)pow(2,add)%2==1) {
        B[wz1]-=pow(2,add);
    }
    if(turn==1 && B[wz1]/(int)pow(2,add)%2==0) {
        B[wz1]+=pow(2,add);
    }
}

// 查询代码：

bool find(int wz) {
    return B[wz/32]/(int)pow(2,wz%32)%2;
}

// 重置代码：

void allReset(int turn) {
    if(turn==0) {
        memset(B,0,sizeof(B));
    }
    if(turn==1) {
        memset(B,0xff,sizeof(B));
    }
}

// 测试：

int main() {
    change(1,1);
    change(2,1);
    cout<<find(2)<<' '<<find(3)<<' '<<find(1)<<endl;
    change(1,0);
    cout<<find(2)<<' '<<find(1)<<endl;
    allReset(1);
    cout<<B[0]<<endl;
    cout<<find(0)<<' '<<find(1)<<' '<<find(31)<<' '<<find(32);
    return 0;
}

Part 2 优化代码：

1. 存储方式：

原代码：

unsigned int B[(100000000+10)/32];

优化：使用位运算，/32 相当于 >>5。

优化代码：

unsigned int B[(100000000+10)>>5];

2. 改变某位置的数：

原代码：

void change(int wz,int turn) {
    int wz1=wz/32,add=wz%32;
    if(turn==0 && B[wz1]/(int)pow(2,add)%2==1) {
        B[wz1]-=pow(2,add);
    }
    if(turn==1 && B[wz1]/(int)pow(2,add)%2==0) {
        B[wz1]+=pow(2,add);
    }
}

优化：

加 inline。
xxx/32 变成 xxx>>5。
xxx%32 变成 xxx&31。
算出 \textrm{add} 后直接 wz>>=5，不用定义变量 \textrm{wz1}。
xxx==0 变成 !xxx。
xxx==1 变成 xxx。
xxx/(int)pow(2,add) 变成 xxx>>1。
xxx%2==1 变成 xxx&1。
xxx%2==0 变成 !(xxx&1)。
pow(2,add) 变成 (1<<add)。
利用“短路”的 &&（不知道咋表达了），if(xx1 && xx2) 当 xx1 为真才会执行 xx2，于是：

if(xx1 && xx2) {
  xx3;
}
可以优化成：

if(xx1 && xx2 && xx3);

优化代码：

inline void change(int wz,int turn) {
    int add=wz&31;
    wz>>=5;
    if(!turn && B[wz]>>add&1 && (B[wz]-=(1<<add)));
    if(turn && !(B[wz]>>add&1) && (B[wz]+=(1<<add)));
}

3. 查询某位置的数：

原代码：

bool find(int wz) {
    return B[wz/32]/(int)pow(2,wz%32)%2;
}

优化：同上文。

优化代码：

inline bool find(int wz) {
    return B[wz>>5]>>(wz&31)&1;
}

4. 清空：

原代码：

void allReset(int turn) {
    if(turn==0) {
        memset(B,0,sizeof(B));
    }
    if(turn==1) {
        memset(B,0xff,sizeof(B));
    }
}

优化：同上文。

优化代码：

inline void allReset(int turn) {
    if(!turn && memset(B,0,sizeof(B)));
    if(turn && memset(B,0xff,sizeof(B)));
}

Part 3 最终代码：

#include<bits/stdc++.h>
using namespace std;

// bool 数组优化空间 

// 一个正整数（unsigned int）化成 2 进制数也可以表示 true/false

unsigned int B[(100000000+10)>>5]; // 100000000 是原始空间 

// unsigned 的最大值是 2^32-1，相当于二进制的 111...11（32 个 1），所以每个 unsigned 都是 32 个 bool 

// 改变代码： 

inline void change(int wz,int turn) {
    int add=wz&31;
    wz>>=5;
    if(!turn && B[wz]>>add&1 && (B[wz]-=(1<<add)));
    if(turn && !(B[wz]>>add&1) && (B[wz]+=(1<<add)));
}

// 查询代码：

inline bool find(int wz) {
    return B[wz>>5]>>(wz&31)&1;
}

// 重置代码：

inline void allReset(int turn) {
    if(!turn && memset(B,0,sizeof(B)));
    if(turn && memset(B,0xff,sizeof(B)));
}

// 测试：

int main() {
    change(1,1);
    change(2,1);
    cout<<find(2)<<' '<<find(3)<<' '<<find(1)<<endl;
    change(1,0);
    cout<<find(2)<<' '<<find(1)<<endl;
    allReset(1);
    cout<<B[0]<<endl;
    cout<<find(0)<<' '<<find(1)<<' '<<find(31)<<' '<<find(32);
    return 0;
}

Part 4 更新：

update at 2021.5.6：

增添 count 函数，是求出整个数组中 0/1 的个数的。

用了一个变量 cnt 表示目前有多少个 1。

在 change 函数中，如果有 1 变成 0 了，--cnt，如果有 0 变成 1 了，++cnt。
在 allReset 函数中，如果全变成 0 了，cnt=0，如果全变成 1 了，cnt=Size 或者数组大小。

代码：

#include<bits/stdc++.h>
using namespace std;

// bool 数组优化空间 

// 一个正整数（unsigned int）化成 2 进制数也可以表示 true/false

const int Size=100000000; // size 是原始空间 

unsigned int B[(Size+32+1)>>5];

// unsigned 的最大值是 2^32-1，相当于二进制的 111...11（32 个 1），所以每个 unsigned 都是 32 个 bool 

int cnt=0; // 为 count(count1/count0)函数用，统计所有 1 的个数 

// 改变代码： 

inline void change(int wz,int turn) {
    int add=wz&31;
    wz>>=5;
    if(!turn && B[wz]>>add&1 && (B[wz]-=(1<<add),--cnt));
    if(turn && !(B[wz]>>add&1) && (B[wz]+=(1<<add),++cnt));
}

// 查询代码：

inline bool find(int wz) {
    return B[wz>>5]>>(wz&31)&1;
}

// 重置代码：

inline void allReset(int turn) {
    if(!turn && (memset(B,0,sizeof(B)),cnt=0));
    if(turn && (memset(B,0xff,sizeof(B)),cnt=size));
}

// 算出 共有多少个 true/false 代码： 

inline int count(int turn) {
    return turn?cnt:Size+32-cnt;
}

// 测试：

int main() {
    change(1,1);
    change(2,1);
    cout<<find(2)<<' '<<find(3)<<' '<<find(1)<<endl;
    change(1,0);
    cout<<find(2)<<' '<<find(1)<<endl;
    allReset(1);
    cout<<B[0]<<endl;
    cout<<find(0)<<' '<<find(1)<<' '<<find(31)<<' '<<find(32)<<endl;
    allReset(0);
    change(0,1);
    change(1,1);
    cout<<count(1)<<' '<<count(0);
    return 0;
}

增添一道自定义模板题，here，能把 bitset 卡飞，我估计是 bitset 的 count 函数不给力。

模板题的代码：

#include<bits/stdc++.h>
using namespace std;

namespace io { // 自己写的 io 优化，为了劳动成果不被摽窃就不公开了
// ......

// bool 数组优化空间 

// 一个正整数（unsigned int）化成 2 进制数也可以表示 true/false

const int Size=1000000000; // size 是原始空间 

unsigned int B[(Size+32+1)>>5];

// unsigned 的最大值是 2^32-1，相当于二进制的 111...11（32 个 1），所以每个 unsigned 都是 32 个 bool 

int n; // 题目里的 n 

int cnt=0; // 为 count(count1/count0)函数用，统计所有 1 的个数 

// 改变代码： 

inline void change(int wz,int turn) {
    int add=wz&31;
    wz>>=5;
    if(!turn && B[wz]>>add&1 && (B[wz]-=(1<<add),--cnt));
    if(turn && !(B[wz]>>add&1) && (B[wz]+=(1<<add),++cnt));
}

// 查询代码：

inline bool find(int wz) {
    return B[wz>>5]>>(wz&31)&1;
}

// 重置代码：

inline void allReset(int turn) {
    if(!turn && (memset(B,0,sizeof(B)),cnt=0));
    if(turn && (memset(B,0xff,sizeof(B)),cnt=n));
}

// 算出 共有多少个 true/false 代码： 

inline int count(int turn) {
    return turn?cnt:n-cnt;
}

// 测试：

int main() {
//  freopen("1.in","r",stdin);
//  freopen("1.out","w",stdout);
    n=read();
    int m=read(),op,a,b;
    for(; m; --m) {
        op=read();
        switch(op) {
            case 1: {
                a=read(),b=read();
                change(a,b);
                break;
            }
            case 2: {
                a=read();
                putchar(find(a)+'0'),putchar('\n');
                break;
            }
            case 3: {
                b=read();
                allReset(b);
                break;
            }
            case 4: {
                b=read();
                write(count(b)),putchar('\n');
                break;
            }
        }
    }
    return 0;
}

update at 2021.5.8：

增加 class，可以定义多个，详见代码：

#include<bits/stdc++.h>
using namespace std;

const int Size=100000000; // Size 是原始空间 

// bool 数组优化空间 

// 一个正整数（unsigned int）化成 2 进制数也可以表示 true/false

class myBitset {
    public :

        unsigned int B[(Size+32+1)>>5];

        // unsigned 的最大值是 2^32-1，相当于二进制的 111...11（32 个 1），所以每个 unsigned 都是 32 个 bool 

        int cnt=0; // 为 count(count1/count0)函数用，统计所有 1 的个数 

        inline void change(int wz,int turn);
        inline bool find(int wz);
        inline void allReset(int turn);
        inline int count(int turn); 
};

// 改变代码： 

inline void myBitset::change(int wz,int turn) {
    int add=wz&31;
    wz>>=5;
    if(!turn && B[wz]>>add&1 && (B[wz]-=(1<<add),--cnt));
    if(turn && !(B[wz]>>add&1) && (B[wz]+=(1<<add),++cnt));
}

// 查询代码：

inline bool myBitset::find(int wz) {
    return B[wz>>5]>>(wz&31)&1;
}

// 重置代码：

inline void myBitset::allReset(int turn) {
    if(!turn && (memset(B,0,sizeof(B)),cnt=0));
    if(turn && (memset(B,0xff,sizeof(B)),cnt=Size));
}

// 算出 共有多少个 true/false 代码： 

inline int myBitset::count(int turn) {
    return turn?cnt:Size+32-cnt;
}

myBitset b,c;

// 测试：

int main() {
    b.change(1,1);
    b.change(2,1);
    cout<<b.find(2)<<' '<<b.find(3)<<' '<<b.find(1)<<endl;
    b.change(1,0);
    cout<<b.find(2)<<' '<<b.find(1)<<endl;
    b.allReset(1);
    cout<<b.find(0)<<' '<<b.find(1)<<' '<<b.find(31)<<' '<<b.find(32)<<endl;
    b.allReset(0);
    b.change(0,1);
    b.change(1,1);
    cout<<b.count(1)<<' '<<b.count(0)<<endl;
    cout<<c.find(0);
    return 0;
}

bug : 长度固定，无法设置。

update at 2021.5.23：

长度不固定啦！可以定义多个。

使用了结构体和 template，这里感谢@SAMSHAWCRAFT 提供技术支持。

template<size_t capacity>

struct myBitset {
    unsigned int B[(capacity+32)>>5];
    int cnt;
    inline void change(int wz,int turn) {
        int add=wz&31;
        wz>>=5;
        if(!turn && B[wz]>>add&1 && (B[wz]-=(1<<add),--cnt));
        if(turn && !(B[wz]>>add&1) && (B[wz]+=(1<<add),++cnt));
    }
    inline bool find(int wz) {
        return B[wz>>5]>>(wz&31)&1;
    }
    inline void allReset(int turn) {
        if(!turn && (memset(B,0,sizeof(B)),cnt=0));
        if(turn && (memset(B,0xff,sizeof(B)),cnt=capacity)); // 这里的 capacity 可以换成想要的大小。
    }
    inline int count(int turn) {
        return turn?cnt:capacity-cnt; // 同上
    }
};
myBitset<1000000000> B,C;

update at 2022.3.28：

我之前写的什么代码啊，change 和 find 的 wz 都反了（应该是 31-wz）。只不过操作当中反了两次回来了导致没有出错。

如果以后用这个模板自己加上些东西，就会挂飞。

改之后的：

template<size_t capacity>

struct myBitset
{
    unsigned int B[(capacity+32)>>5];
    int cnt;
    inline void change(int wz,int turn)
    {
        int add=31-(wz&31);
        wz>>=5;
        if(!turn && B[wz]>>add&1 && (B[wz]-=(1<<add),--cnt));
        if(turn && !(B[wz]>>add&1) && (B[wz]+=(1<<add),++cnt));
    }
    inline bool find(int wz)
    {
        return B[wz>>5]>>(31-(wz&31))&1;
    }
    inline void allReset(int turn)
    {
        if(!turn && (memset(B,0,sizeof(B)),cnt=0));
        if(turn && (memset(B,0xff,sizeof(B)),cnt=capacity)); // 这里的 capacity 可以换成想要的大小
    }
    inline int count(int turn)
    {
        return turn?cnt:capacity-cnt; // 同上
    }
    inline void range_qf(int r) // 区间取反
    {
        int wz=(r>>5);
        for(int i=0; i<wz; ++i) B[i]=~B[i];
        for(int i=(wz<<5); i<=r; ++i)
        {
            int now=(wz+1<<5)-1-i;
            if((B[wz]>>now)&1) B[wz]-=(1<<now);
            else B[wz]+=(1<<now);
        }
    }
    inline int range_count(int r) // 区间求 count
    {
        int wz=(r>>5),sum=0;
        for(int i=0; i<wz; ++i) sum+=__builtin_popcountll(B[i]);
        for(int i=(wz<<5); i<=r; ++i)
        {
            int now=(wz+1<<5)-1-i;
            sum+=((B[wz]>>now)&1);
        }
        return sum;
    }
};
myBitset<200010> b;