bitset（C++实现）-创新互联

1. bitset类 1.1 私有成员

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

创新互联公司是一家集网站建设,青阳企业网站建设,青阳品牌网站建设,网站定制,青阳网站建设报价,网络营销,网络优化,青阳网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。
template// N个比特位	
class bitset
{private:
    vector_bits; // 以char为单位管理
};
1. bitset接口 1.1 构造函数

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

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

image-20221214231228921

申请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或运算。

image-20221214233629654

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个个数。

image-20221215160806990

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

源代码

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章标题：bitset（C++实现）-创新互联
网站路径：https://www.cdcxhl.com/article14/cejpde.html

成都网站建设公司_创新互联，为您提供定制网站、App开发、软件开发、网站导航、网站建设、自适应网站

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

搜索引擎优化

ChatGPT知识

各行业网站