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