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++函数执行时间统计工具,希望对大家有所帮助... 目录前言工具特性核心设计1. 数据结构设计2. 单例模式管理器3. RAII自动计时使用方法基本用法高级用法
阅读更多...
深入解析C++ 中std::map内存管理

深入解析C++ 中std::map内存管理

《深入解析C++中std::map内存管理》文章详解C++std::map内存管理,指出clear()仅删除元素可能不释放底层内存,建议用swap()与空map交换以彻底释放,针对指针类型需手动de... 目录1️、基本清空std::map2️、使用 swap 彻底释放内存3️、map 中存储指针类型的对象
阅读更多...
C++ STL-string类底层实现过程

C++ STL-string类底层实现过程

《C++STL-string类底层实现过程》本文实现了一个简易的string类,涵盖动态数组存储、深拷贝机制、迭代器支持、容量调整、字符串修改、运算符重载等功能,模拟标准string核心特性,重点强... 目录实现框架一、默认成员函数1.默认构造函数2.构造函数3.拷贝构造函数(重点)4.赋值运算符重载函数
阅读更多...
C++ vector越界问题的完整解决方案

C++ vector越界问题的完整解决方案

《C++vector越界问题的完整解决方案》在C++开发中,std::vector作为最常用的动态数组容器,其便捷性与性能优势使其成为处理可变长度数据的首选,然而,数组越界访问始终是威胁程序稳定性的... 目录引言一、vector越界的底层原理与危害1.1 越界访问的本质原因1.2 越界访问的实际危害二、基
阅读更多...
c++日志库log4cplus快速入门小结

c++日志库log4cplus快速入门小结

《c++日志库log4cplus快速入门小结》文章浏览阅读1.1w次，点赞9次，收藏44次。本文介绍Log4cplus，一种适用于C++的线程安全日志记录API，提供灵活的日志管理和配置控制。文章涵盖... 目录简介日志等级配置文件使用关于初始化使用示例总结参考资料简介log4j 用于Java，log4c
阅读更多...
C++归并排序代码实现示例代码

C++归并排序代码实现示例代码

《C++归并排序代码实现示例代码》归并排序将待排序数组分成两个子数组,分别对这两个子数组进行排序,然后将排序好的子数组合并,得到排序后的数组,：本文主要介绍C++归并排序代码实现的相关资料,需要的... 目录1 算法核心思想2 代码实现3 算法时间复杂度1 算法核心思想归并排序是一种高效的排序方式，需要用
阅读更多...
C++11范围for初始化列表auto decltype详解

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3
阅读更多...
C++11右值引用与Lambda表达式的使用

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发；同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符
阅读更多...
C++中detach的作用、使用场景及注意事项

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()？它的作用是什么？类比一下：二、join()的作用总结三、join()怎么
阅读更多...
C++中全局变量和局部变量的区别

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2