c++手写的bitset

2024-06-10 23:52
文章标签 c++ 手写 bitset

本文主要是介绍c++手写的bitset，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

支持stl bitset 类似的api

#include <iostream>
#include <vector>
#include <climits>
#include <utility>
#include <stdexcept>
#include <iterator>using namespace std;const int W = 64;class Bitset {
private:vector<unsigned long long> a;int numBits;int highBit(unsigned long long x) const {return W - 1 - __builtin_clzll(x);}int lowBit(unsigned long long x) const {return __builtin_ffsll(x) - 1;}public:Bitset(int size) : a((size + W - 1) / W, 0), numBits(size) {}// Copy constructorBitset(const Bitset& other) : a(other.a), numBits(other.numBits) {}// Copy assignment operatorBitset& operator=(const Bitset& other) {if (this != &other) {a = other.a;numBits = other.numBits;}return *this;}// Move constructorBitset(Bitset&& other) noexcept : a(std::move(other.a)), numBits(other.numBits) {other.numBits = 0;}void applyShiftLeft(int shift, int start, int end) {if (shift == 0) return;int startBlock = start / W;int endBlock = (end - 1) / W;int startOffset = start % W;int endOffset = (end - 1) % W + 1;if (shift >= end - start) {for (int i = startBlock; i <= endBlock; ++i) {a[i] &= ~(((1ull << (min(endOffset, W) - (i == startBlock ? startOffset : 0))) - 1) << (i == startBlock ? startOffset : 0));}return;}int blockShift = shift / W;int bitShift = shift % W;for (int i = endBlock; i >= startBlock; --i) {unsigned long long newValue = 0;if (i - blockShift >= startBlock) {newValue |= (a[i - blockShift] << bitShift);if (bitShift && i - blockShift - 1 >= startBlock) {newValue |= (a[i - blockShift - 1] >> (W - bitShift));}}if (i == startBlock) {newValue &= (((1ull << (min(endOffset, W) - startOffset)) - 1) << startOffset);}a[i] &= ~(((1ull << (min(endOffset, W) - (i == startBlock ? startOffset : 0))) - 1) << (i == startBlock ? startOffset : 0));a[i] |= newValue;}}void applyShiftRight(int shift, int start, int end) {if (shift == 0) return;int startBlock = start / W;int endBlock = (end - 1) / W;int startOffset = start % W;int endOffset = (end - 1) % W + 1;if (shift >= end - start) {for (int i = startBlock; i <= endBlock; ++i) {a[i] &= ~(((1ull << (min(endOffset, W) - (i == startBlock ? startOffset : 0))) - 1) << (i == startBlock ? startOffset : 0));}return;}int blockShift = shift / W;int bitShift = shift % W;for (int i = startBlock; i <= endBlock; ++i) {unsigned long long newValue = 0;if (i + blockShift <= endBlock) {newValue |= (a[i + blockShift] >> bitShift);if (bitShift && i + blockShift + 1 <= endBlock) {newValue |= (a[i + blockShift + 1] << (W - bitShift));}}if (i == startBlock) {newValue &= (((1ull << (min(endOffset, W) - startOffset)) - 1) << startOffset);}a[i] &= ~(((1ull << (min(endOffset, W) - (i == startBlock ? startOffset : 0))) - 1) << (i == startBlock ? startOffset : 0));a[i] |= newValue;}}// Move assignment operatorBitset& operator=(Bitset&& other) noexcept {if (this != &other) {a = std::move(other.a);numBits = other.numBits;other.numBits = 0;}return *this;}// 支持 << 区间Bitset operator<<(int shift) const {Bitset res = *this;res <<= shift;return res;}// 支持 >> 区间Bitset operator>>(int shift) const {Bitset res = *this;res >>= shift;return res;}// 支持 <<=Bitset& operator<<=(int shift) {if (shift >= numBits) {fill(a.begin(), a.end(), 0);return *this;}applyShiftLeft(shift, 0, numBits);return *this;}// 支持 >>=Bitset& operator>>=(int shift) {if (shift >= numBits) {fill(a.begin(), a.end(), 0);return *this;}applyShiftRight(shift, 0, numBits);return *this;}// 支持 []bool operator[](int index) const {if (index < 0 || index >= numBits) {throw out_of_range("Index out of range");}int blockIndex = index / W;int bitIndex = index % W;return (a[blockIndex] >> bitIndex) & 1;}// 支持从高到低的第一个置位int highestSetBit() const {for (int i = a.size() - 1; i >= 0; --i) {if (a[i] != 0) {return min(i * W + highBit(a[i]), numBits - 1);}}return -1;}// 支持从高到低的下一个置位int nextHighestSetBit(int index) const {if (index < 0 || index >= numBits) {return -1;}int blockIndex = index / W;int bitIndex = index % W;unsigned long long mask = (1ull << bitIndex) - 1;if ((a[blockIndex] & mask) != 0) {return blockIndex * W + highBit(a[blockIndex] & mask);}for (int i = blockIndex - 1; i >= 0; --i) {if (a[i] != 0) {return i * W + highBit(a[i]);}}return -1;}// 支持从低到高的第一个置位int lowestSetBit() const {for (int i = 0; i < a.size(); ++i) {if (a[i] != 0) {return min(i * W + lowBit(a[i]), numBits - 1);}}return -1;}// 支持从低到高的下一个置位int nextLowestSetBit(int index) const {if (index < 0 || index >= numBits) {return -1;}int blockIndex = index / W;int bitIndex = index % W;unsigned long long mask = ~((1ull << (bitIndex + 1)) - 1);if ((a[blockIndex] & mask) != 0) {return blockIndex * W + lowBit(a[blockIndex] & mask);}for (int i = blockIndex + 1; i < a.size(); ++i) {if (a[i] != 0) {return i * W + lowBit(a[i]);}}return -1;}// 支持 countint count() const {int cnt = 0;for (auto block : a) {cnt += __builtin_popcountll(block);}return cnt;}// 支持 anybool any() const {for (auto block : a) {if (block != 0) {return true;}}return false;}// 支持 nonebool none() const {return !any();}// 支持 allbool all() const {for (int i = 0; i < numBits; ++i) {if (!(*this)[i]) {return false;}}return true;}// 支持 flipvoid flip() {for (auto& block : a) {block = ~block;}// Make sure no bits beyond numBits are setif (numBits % W != 0) {a.back() &= (1ull << (numBits % W)) - 1;}}// 支持 flip(int index)void flip(int index) {if (index < 0 || index >= numBits) {throw out_of_range("Index out of range");}int blockIndex = index / W;int bitIndex = index % W;a[blockIndex] ^= (1ull << bitIndex);}// 支持 set(int index)void set(int index) {if (index < 0 || index >= numBits) {throw out_of_range("Index out of range");}int blockIndex = index / W;int bitIndex = index % W;a[blockIndex] |= (1ull << bitIndex);}// 支持 set(int index, bool value)void set(int index, bool value) {if (value) {set(index);} else {reset(index);}}// 支持 set()void set() {for (auto& block : a) {block = ~0ull;}// Make sure no bits beyond numBits are setif (numBits % W != 0) {a.back() &= (1ull << (numBits % W)) - 1;}}// 支持 reset(int index)void reset(int index) {if (index < 0 || index >= numBits) {throw out_of_range("Index out of range");}int blockIndex = index / W;int bitIndex = index % W;a[blockIndex] &= ~(1ull << bitIndex);}// 支持 reset()void reset() {fill(a.begin(), a.end(), 0);}// 支持 |=Bitset& operator|=(const Bitset& other) {if (numBits != other.numBits) {throw invalid_argument("Bitsets must be of the same size");}for (int i = 0; i < a.size(); ++i) {a[i] |= other.a[i];}return *this;}// 支持 |Bitset operator|(const Bitset& other) const {Bitset res = *this;res |= other;return res;}// 支持 &=Bitset& operator&=(const Bitset& other) {if (numBits != other.numBits) {throw invalid_argument("Bitsets must be of the same size");}for (int i = 0; i < a.size(); ++i) {a[i] &= other.a[i];}return *this;}// 支持 &Bitset operator&(const Bitset& other) const {Bitset res = *this;res &= other;return res;}// 支持 ^=Bitset& operator^=(const Bitset& other) {if (numBits != other.numBits) {throw invalid_argument("Bitsets must be of the same size");}for (int i = 0; i < a.size(); ++i) {a[i] ^= other.a[i];}return *this;}// 支持 ^Bitset operator^(const Bitset& other) const {Bitset res = *this;res ^= other;return res;}// 支持 ~Bitset operator~() const {Bitset res = *this;for (int i = 0; i < a.size(); ++i) {res.a[i] = ~a[i];}if (numBits % W != 0) {res.a.back() &= (1ull << (numBits % W)) - 1;}return res;}// 支持 sizeint size() const {return numBits;}// 支持 testbool test(int index) const {return (*this)[index];}// 支持 to_ullongunsigned long long to_ullong() const {if (numBits > W) {throw overflow_error("Bitset size exceeds unsigned long long capacity");}return a[0];}// 支持 to_ulongunsigned long to_ulong() const {if (numBits > sizeof(unsigned long) * CHAR_BIT) {throw overflow_error("Bitset size exceeds unsigned long capacity");}return static_cast<unsigned long>(a[0]);}// 支持 print（用于调试）void print() const {for (int i = 0; i < numBits; ++i) {cout << (*this)[i];if ((i + 1) % W == 0) cout << " ";}cout << endl;}class iterator {public:using iterator_category = bidirectional_iterator_tag;using difference_type = int;using value_type = int;using pointer = const int*;using reference = const int&;private:const Bitset* bitset;int index;public:iterator(const Bitset* bitset, int index) : bitset(bitset), index(index) {}value_type operator*() const { return index; }iterator& operator++() {index = bitset->nextLowestSetBit(index);return *this;}iterator operator++(int) {iterator tmp = *this;++(*this);return tmp;}iterator& operator--() {if (index == -1) {index = bitset->highestSetBit();} else {index = bitset->nextHighestSetBit(index);}return *this;}iterator operator--(int) {iterator tmp = *this;--(*this);return tmp;}friend bool operator==(const iterator& a, const iterator& b) {return a.index == b.index;}friend bool operator!=(const iterator& a, const iterator& b) {return a.index != b.index;}};class reverse_iterator {public:using iterator_category = bidirectional_iterator_tag;using difference_type = int;using value_type = int;using pointer = const int*;using reference = const int&;private:const Bitset* bitset;int index;public:reverse_iterator(const Bitset* bitset, int index) : bitset(bitset), index(index) {}value_type operator*() const { return index; }reverse_iterator& operator++() {index = bitset->nextHighestSetBit(index);return *this;}reverse_iterator operator++(int) {reverse_iterator tmp = *this;++(*this);return tmp;}reverse_iterator& operator--() {if (index == -1) {index = bitset->lowestSetBit();} else {index = bitset->nextLowestSetBit(index);}return *this;}reverse_iterator operator--(int) {reverse_iterator tmp = *this;--(*this);return tmp;}friend bool operator==(const reverse_iterator& a, const reverse_iterator& b) {return a.index == b.index;}friend bool operator!=(const reverse_iterator& a, const reverse_iterator& b) {return a.index != b.index;}};iterator begin() const {return iterator(this, lowestSetBit());}iterator end() const {return iterator(this, -1);}reverse_iterator rbegin() const {return reverse_iterator(this, highestSetBit());}reverse_iterator rend() const {return reverse_iterator(this, -1);}
};int main() {Bitset bs(12);bs.set(10);cout << bs.highestSetBit() <<endl;bs.flip();for (auto it = bs.begin(); it != bs.end(); it++) {cout << *it << "\t";}cout << endl;for (auto it = bs.rbegin(); it != bs.rend(); it++) {cout << *it << "\t";}cout << endl;bitset<100> cs;cs.set();cs.set(1, 1);
}

这篇关于c++手写的bitset的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1049624。

相关文章

【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
【C++高阶】C++类型转换全攻略：深入理解并高效应用

【C++高阶】C++类型转换全攻略：深入理解并高效应用

📝个人主页🌹：Eternity._ ⏩收录专栏⏪：C++ “ 登神长阶 ” 🤡往期回顾🤡：C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝
阅读更多...
C++——stack、queue的实现及deque的介绍

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现
阅读更多...
c++的初始化列表与const成员

c++的初始化列表与const成员

初始化列表与const成员 const成员 使用const修饰的类、结构、联合的成员变量，在类对象创建完成前一定要初始化。 不能在构造函数中初始化const成员，因为执行构造函数时，类对象已经创建完成，只有类对象创建完成才能调用成员函数，构造函数虽然特殊但也是成员函数。 在定义const成员时进行初始化，该语法只有在C11语法标准下才支持。 初始化列表 在构造函数小括号后面，主要用于给
阅读更多...
2024/9/8 c++ smart

2024/9/8 c++ smart

1.通过自己编写的class来实现unique_ptr指针的功能 #include <iostream> using namespace std; template<class T> class unique_ptr { public:         //无参构造函数         unique_ptr();         //有参构造函数         unique_ptr(
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2