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#如何调用C++库

C#如何调用C++库

《C#如何调用C++库》：本文主要介绍C#如何调用C++库方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录方法一：使用P/Invoke1. 导出C++函数2. 定义P/Invoke签名3. 调用C++函数方法二：使用C++/CLI作为桥接1. 创建C++/CL
阅读更多...
C++如何通过Qt反射机制实现数据类序列化

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类，并对数据类进行存储、打印、调试等操作。由于数据类
阅读更多...
Linux下如何使用C++获取硬件信息

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息：读取"/proc/cpuinfo"文件获取磁盘信息：读取"/proc/diskstats"文
阅读更多...
C++使用printf语句实现进制转换的示例代码

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符（formatspecifier）快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指
阅读更多...
C++中初始化二维数组的几种常见方法

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a
阅读更多...
C++ vector的常见用法超详细讲解

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》：本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve
阅读更多...
如何高效移除C++关联容器中的元素

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元
阅读更多...
Python获取C++中返回的char*字段的两种思路

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串，目前我找到两种解决问题的思路，具体实现如下：
阅读更多...
C++ Sort函数使用场景分析

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序
阅读更多...
Java调用C++动态库超详细步骤讲解(附源码)

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,：本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步：动态库生成（vs2017+qt5.12.10）第二步：Java调用C++
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2