bitset中_Find_first()与_Find_next()函数

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。如果有知道的大佬欢迎在评论区留言，本蒟蒻感激不尽

参考资料

bitset find_first and find_next