当前位置: 首页 > news >正文

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

支持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 …...

【机器学习系列】深入理解集成学习:从Bagging到Boosting

目录 一、集成方法的一般思想 二、集成方法的基本原理 三、构建集成分类器的方法 常见的有装袋&#xff08;Bagging&#xff09;和提升&#xff08;Boosting&#xff09;两种方法 方法1 &#xff1a;装袋&#xff08;Bagging&#xff09; Bagging原理如下图&#xff1a; …...

用FFMPEG对YUV序列进行编辑的笔记

还是单独开一个吧 每次找挺烦的 播放YUV序列 ffmpeg -f rawvideo -pix_fmt yuv420p -s 3840x2160 -i "Wood.yuv" -vf "scale1280x720" -c:v rawvideo -pix_fmt yuv420p -f sdl "Wood"4K序列转720P ffmpeg -f rawvideo -pix_fmt yuv420p -s 38…...

智能投顾:重塑金融理财市场,引领行业新潮流

一、引言 在数字化浪潮的推动下,金融行业正经历着前所未有的变革。其中,智能投顾作为金融科技的重要分支,以其高效、便捷和个性化的服务,逐渐成为金融理财市场的新宠。本文旨在探讨智能投顾如何引领金融理财新潮流,通过丰富的案例及解决方案,展示其独特的魅力和价值。 二…...

iOS18 新变化提前了解,除了AI还有这些变化

iOS 18即将在不久的将来与广大iPhone用户见面&#xff0c;这次更新被普遍认为是苹果历史上最重要的软件更新之一。据多方报道和泄露的消息&#xff0c;iOS 18将带来一系列全新的功能和改进&#xff0c;包括在人工智能领域的重大突破、全新的设计元素以及增强的性能和安全性。现…...

力扣算法题:多数元素 --多语言实现

无意间看到&#xff0c;力扣存算法代码居然还得升级vip。。。好吧&#xff0c;我自己存吧 golang&#xff1a; func majorityElement(nums []int) int {count : 0condidate : 0for _,val : range nums {if count 0 {condidate valcount 1} else if val condidate {count} …...

[Kubernetes] 容器运行时 Container Runtime

文章目录 1.容器运行时(Container Runtime)2.容器运行时接口3.容器运行时层级4.容器运行时比较5.强隔离容器6.K8S为何难以实现真正的多租户 1.容器运行时(Container Runtime) Container Runtime 是运行于 k8s 集群每个节点中&#xff0c;负责容器的整个生命周期。Docker 就目前…...

10进制与二、八、十六进制的转换

x进制转10进制 1、如八进制数123&#xff0c;通过把每一位数字和8的指数级进行相乘 1 * 8^2 2 * 8^1 3 * 8^01 * 64 2 * 8 3 * 164 16 383 2、十六进制1A3 1 * 16^2 A(即10) * 16^1 3 * 16^01 * 256 10 * 16 3 * 1256 160 3419 3、二进制1010 1 * 2^3 0 * 2…...

日常实习-小米计算机视觉算法岗面经

文章目录 流程问题请你写出项目中用到的模型代码&#xff0c;Resnet50&#xff08;1&#xff09;网络退化现象&#xff1a;把网络加深之后&#xff0c;效果反而变差了&#xff08;2&#xff09;过拟合现象&#xff1a;训练集表现很棒&#xff0c;测试集很差 把你做的工作里面的…...

(C++)string模拟实现

string底层是一个是字符数组 为了跟库里的string区别&#xff0c;所以定义一个命名空间将类string包含 一、构造 1.构造函数 注意&#xff1a;将char*传给const char*是范围缩小&#xff0c;因此只能1&#xff1a;1构造一个 strlen遇到nullptr解引用会报错&#xff0c;因此…...

类和对象的学习总结(一)

面向对象和面向过程编程初步认识 C语言是面向过程的&#xff0c;关注过程&#xff08;分析求解问题的步骤&#xff09; 例如&#xff1a;外卖&#xff0c;关注点菜&#xff0c;接单&#xff0c;送单等 C是面向对象的&#xff0c;关注对象&#xff0c;把一件事拆分成不同的对象&…...

力扣22. 括号生成

数字 n 代表生成括号的对数&#xff0c;请你设计一个函数&#xff0c;用于能够生成所有可能的并且有效的括号组合。 示例 1&#xff1a;输入&#xff1a;n 3 输出&#xff1a;["((()))","(()())","(())()","()(())","()()(…...

检测窗口是否最大化兼容 Win10/11

检测窗口是否最大化&#xff08;窗口覆盖或独占全屏&#xff09;兼容 Win10/11 问题描述 在 Win10/11 上有很多 UWP 进程&#xff0c;检测窗口是否最大化将迎来新的挑战。这些窗口以其不能够使用 Win32 的 IsWindowVisible 获取窗口可见性为特征。此时&#xff0c;必须使用 D…...

【qsort函数】

前言 我们要学习qsort函数并利用冒泡函数仿照qsort函数 首先我们要了解一下qsort&#xff08;快速排序&#xff09; 这是函数的的基本参数 void qsort (void* base, size_t num, size_t size,int (*compar)(const void*,const void*)); 简单解释一下 base&#xff1a;指向…...

python类元编程示例-使用类型注解来检查转换属性值的类框架

用三种方式实现使用类型注解来检查转换属性值的类框架 1 __init_subclass__方式 1.1 代码实现 from collections.abc import Callable # <1> from typing import Any, NoReturn, get_type_hints from typing import Dict, Typeclass Field:def __init__(self, name: …...

Python3 笔记:字符串的 zfill() 和 rjust()

1、zfill() 方法返回指定长度的字符串&#xff0c;原字符串右对齐&#xff0c;前面填充0。 语法&#xff1a;str.zfill(width) width &#xff1a;指定字符串的长度。原字符串右对齐&#xff0c;前面填充0。 str1 2546 str2 2 print(str1.zfill(10)) # 运行结果&#xff1…...

SpringBoot项目启动提示端口号占用

Windows环境下&#xff0c;SpringBoot项目启动时报端口号占用&#xff1a; *************************** APPLICATION FAILED TO START ***************************Description:Web server failed to start. Port 8080 was already in use.Action:Identify and stop the proc…...

音视频开发23 FFmpeg 音频重采样

代码实现的功能 目的是 将&#xff1a; 一个采样率为 44100&#xff0c;采样通道为 2&#xff0c;格式为 AV_SAMPLE_FMT_DBL 的 in.pcm 数据 转换成 一个采样率为 48000&#xff0c;采样通道为 1&#xff0c;格式为 AV_SAMPLE_FMT_S16 的 out.pcm 数据 1.重采样 1.1 为什么要重…...

windows系统下安装fnm

由于最近做项目要切换多个node版本&#xff0c;查询了一下常用的有nvm和fnm这两种&#xff0c;对比了一下选择了fnm。 下载fnm 有两种方式&#xff0c;目前最新版本是1.37.0&#xff1a; 1.windows下打开powershell&#xff0c;执行以下命令下载fnm winget install Schniz.f…...

【Linux网络】传输层协议 - UDP

文章目录 一、传输层&#xff08;运输层&#xff09;运输层的特点复用和分用再谈端口号端口号范围划分认识知名端口号&#xff08;Well-Know Port Number&#xff09;两个问题① 一个进程是否可以绑定多个端口号&#xff1f;② 一个端口号是否可以被多个进程绑定&#xff1f; n…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...