bitset(C++实现)

简介: bitset(C++实现)

1. bitset类

1.1 私有成员

位图实际上就是一个指定比特位个数的连续内存空间,所以可以用STL内置的容器vector管理,除此之外,理论上任何类型都可以作为元素的类型,只不过为了容易理解,它的每个元素的类型被设定为char。

template<size_t N>    // N个比特位  
class bitset
{
private:
    vector<char> _bits; // 以char为单位管理
};

1. bitset接口

1.1 构造函数

构造一个有N位的位图,并将所有位初始化为0。

由于申请空间时的最小单位是char(1字节),也就是8个比特位。那么对于N个比特位,需要申请N/8+1个char型空间,因为N可能不是8的整数倍。

申请N=20个比特位,需要20/8+1=3个char。

bitset()
{
    _bits.resize(N / 8 + 1, 0);
}

1.2 set

要把某个比特位变成1,首先要知道这个比特位在哪个位置。

  1. 首先计算这个比特位在整个位图中的第x个char;
  2. 然后计算比特位在这个char的第y个位置;
  3. 最后将1左移y位和第x个char运算。

void set(size_t pos)
{
    assert(pos < N);
    size_t x = pos / 8;   // 在x个char
    size_t y = pos % 8;   // 在这个char的第y个比特位
    _bits[x] |= (1 << y); // 将这个比特位设为1
}

1.3 reset

要把某个比特位清空,即恢复到0状态,首先要找到它的位置,和set的操作是一样的,只有最后一步不同:

  1. 首先计算这个比特位在整个位图中的第x个char;
  2. 然后计算比特位在这个char的第y个位置;
  3. 最后将1左移y位后,整体取反,再和第x个char运算。

注意:

使用~对左移后的1按位取反,而不是逻辑取反!

void reset(size_t pos)
{
    assert(pos < N);
    size_t x = pos / 8;     // 在x个char
    size_t y = pos % 8;     // 在这个char的第y个比特位
    _bits[x] &= (~(1 << y));  // 将这个比特位设为0
}

1.4 flip

要把某个比特位取反,首先要找到它的位置:

  1. 首先计算这个比特位在整个位图中的第x个char;
  2. 然后计算比特位在这个char的第y个位置;
  3. 最后将1左移y位后,再和第x个char异或运算。
void flip(size_t pos)
{
    assert(pos < N);
    size_t x = pos / 8;     // 在x个char
    size_t y = pos % 8;     // 在这个char的第y个比特位
    _bits[x] ^= (1 << y);   // 将这个比特位取反
}

1.5 test

同样地:

  1. 首先计算这个比特位在整个位图中的第x个char;
  2. 然后计算比特位在这个char的第y个位置;
  3. 获取某个位的状态:
  • true:已被设置;
  • false:未被设置。
void test(size_t pos)
{
    assert(pos < N);
    size_t x = pos / 8;     // 在x个char
    size_t y = pos % 8;     // 在这个char的第y个比特位
    if (_bits[x] & (1 << y))  // 该位已被设置
        return true;
    else
        return false;
}

1.6 size、count

  • size:获取位图中可以容纳的位的个数。

直接返回模板参数N。

size_t size()
{
    return N;
}
  • count:获取位图中被设置的位的个数。

要知道位图中被设置为1的位的个数,就是遍历整个位图,统计1的个数。

  1. 将当前数x与x-1与运算得到新的数x;
  2. x是否为0:
  1. 为0:结束;
  2. 不为0:重复操作。

原因是每进行一次操作1,都会将数x最右端的1消去。那么在x不为0之前,进行了几次消1操作就是位图中1个个数。

size_t count()
{
    size_t count = 0;
    for (auto e : _bits)
    {
        char num = e;
        while (num)
        {
            num &= num - 1;
            count++;
        }
    }
    return count;
}

1.7 any、none、all

  • any:判断位图中是否有任何位被设置。

只需要遍历位图中所有的比特位,一旦有1则返回true,否则返回0。但也可以不用这么干,因为一个char里只要有一个不为0,整个char就是其他字符。ASCII=0对应的字符时'\0',但是它一般用在字符串处理中,个人认为在这里还是将0强转为char比较合适。

bool any()
{
    for (auto e : _bits)
    {
        if (e != (char)0)
            return true;
    }
    return false;
}
  • none:判断位图中是否全部位都没有被设置。

直接复用any的代码,它们是互斥的。

bool none()
{
    return !any();
}
  • 判断位图中是否全部位都被设置。

判断全部位置都被设置为1,分为两步:

  1. 判断所有完整的char中8个比特位是否都为1;
  2. 判断剩下(可能)不完整的char的所有比特位是否都为1。

同样地,第一步中可以判断这个char是否等于比特位全为1对应的字符,也就是(char)127,遍历剩下的比特位是否为1即可。

bool all()
{
    size_t size = _bits.size();
    for (size_t i = 0; i < size - 1; i++) // 前size-1个完整的char
    {
        if (_bits[i] != (char)127)
            return false;
    }
    for (size_t i = 0; i < N % 8; i++)    // 最后一个char的剩下位
    {
        if ((_bits[size - 1] & (1 << i)) == (char)0)
            return false;
    }
    return true;
}

1.8 打印函数

这不是bitset内置的成员函数,因为STL中重载了流输入>>和流输出<<运算符,可以直接打印bitset中的内容,而模拟实现并未重载它们,所以用打印函数输出容器内容。

思路和上一个很类似,也是分批打印:

void Print()
{
    string ret = "";
    size_t size = _bits.size();
    for (size_t i = 0; i < size - 1; i++)
    {
        for (size_t j = 0; j < 8; j++)
        {
            if (_bits[i] & (1 << j))
                ret += "1";
            else
                ret += "0";
        }
    }
    for (size_t j = 0; j < N % 8; j++)
    {
        if (_bits[size - 1] & (1 << j))
            ret += "1";
        else
            ret += "0";
    }
    cout << ret << endl;
}

2. bitset测试

void bitset_test1()
{
  xy::bitset<30> bs1;
  bs1.set(8);
  bs1.set(9);
  bs1.set(7);
  bs1.set(27);
  bs1.set(20);
  bs1.Print();
  cout << bs1.count() << endl;
  bs1.reset(8);
  bs1.reset(9);
  bs1.reset(20);
  bs1.Print();
  cout << bs1.count() << endl;
  cout << bs1.any() << endl;
  bs1.reset(7);
  bs1.reset(27);
  bs1.Print();
  cout << bs1.none() << endl;
}

输出:

000000011100000000001000000100
5
000000010000000000000000000100
2
1
000000000000000000000000000000
1

源代码

目录
相关文章
|
3月前
|
人工智能 Linux Go
window 部署 coze-loop
本教程介绍了如何在 Linux 系统上安装 Go 环境、Docker 以及 Coze Loop,并配置多模型运行。内容包括安装步骤、环境变量设置、代码拉取、模型配置及服务启动等关键流程,适用于搭建本地化的 AI 模型服务环境。
364 7
window 部署 coze-loop
|
弹性计算 监控 数据挖掘
事件驱动架构的优势与应用:深度解析与实战应用
【8月更文挑战第17天】事件驱动架构以其松耦合、可扩展性、异步处理、实时性和高可靠性等优势,在实时数据处理、复杂业务流程、弹性伸缩和实时通信等多个领域展现出巨大的应用潜力。通过合理应用事件驱动架构,可以构建灵活、可扩展和可维护的系统架构,满足不断变化的业务需求和技术挑战。对于开发者而言,深入理解事件驱动架构的核心概念和优势,将有助于更好地设计和实现高质量的软件系统。
|
机器学习/深度学习 计算机视觉
【机器学习】LoFTR:革命性图像特征批评技术等领跑者
【机器学习】LoFTR:革命性图像特征批评技术等领跑者
448 1
|
存储 安全 算法
三种常见的加密算法:MD5、对称加密与非对称加密的比较与应用
网络安全聚焦加密算法:MD5用于数据完整性校验,易受碰撞攻击;对称加密如AES快速高效,密钥管理关键;非对称加密如RSA提供身份验证,速度慢但安全。三种算法各有所长,适用场景各异,安全与效率需权衡。【6月更文挑战第17天】
2418 2
|
算法 数据处理 流计算
流计算引擎数据问题之传播模块工作如何解决
流计算引擎数据问题之传播模块工作如何解决
93 1
|
数据采集 算法 数据处理
LabVIEW软件开发任务的工作量估算方法
LabVIEW软件开发任务的工作量估算方法
207 1
|
消息中间件 Java Maven
SpringBoot整合RabbitMQ实现死信队列
前面一文通过[Java整合RabbitMQ实现生产消费(7种通讯方式)](https://wangbinguang.blog.csdn.net/article/details/128284902),本文基于SpringBoot实现RabbitMQ中的死信队列和延迟队列。
303 0
|
C++
C++Qt | 无法打开源文件:“x64\Debug\moc_xxx.cpp”怎么办。
编译时报错: 1>c1xx : fatal error C1083: 无法打开源文件:“x64\Debug\Res\src\Vlc\include\moc_AVPlayer.cpp”: No such file or directory的解决办法。
730 0
|
网络虚拟化 网络架构
华为三层交换机配置不同网段互通
一般情况下,三层交换机不直接连终端端,太浪费了,可以连一个交换机然后再连终端
630 0
华为三层交换机配置不同网段互通
|
存储 算法 分布式数据库
HBase 加载Hfile时的读取过程
Hfile分为4部分,其中loadOnOpen section 和trailer这2部分是open file时就会加载到内存的,本文简述其读取步骤。
2061 0
HBase 加载Hfile时的读取过程