bitset中_Find_first()与_Find_next()函数
很有趣但是没怎么有用的两个函数。
_Find_fisrt就是找到从低位到高位第一个1的位置
#include<bits/stdc++.h>
int main() {
std::bitset<1001> B;
B.set(2); B.set(4); B.set(233);
std::cout << B._Find_first();
}
输出结果为2
_Find_next就是找到当前位置的下一个1的位置
#include<bits/stdc++.h>
int main() {
std::bitset<1001> B;
B.set(2); B.set(4); B.set(233);
std::cout << B._Find_next(5);
}
输出结果为233 1001，也就是说如果某个元素之后没有元素的话会返回bitset的大小
那么我们可以这样去遍历一个bitset
#include<bits/stdc++.h>
int main() {
std::bitset<1001> B;
B.set(2); B.set(4); B.set(233);
for(int i = B._Find_first(); i != B.size(); i = B._Find_next(i))
std::cout << i << ' ';
}
输出结果为2 4 233。
按照糖教主的说法，这样遍历的复杂度是\(O(\frac{n}{w})\)的。\(n\)是bitset的大小，\(w\)与计算机有关，一般为\(32\)或\(64\)。也就是说遍历bitset的复杂度与bitset内1的个数无关
同时Swistakk大佬说
I don’t remember it in details, but bitset in fact has a function for k-th bit, however it is declared as private… I have no idea why would someone not expose such useful function to world and deem it as private, but #define private public is there to help you
但是我翻了半天bitset的源代码也没找到与第K有关的函数qwq。如果有知道的大佬欢迎在评论区留言，本蒟蒻感激不尽
