欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

bitset中_Find_first()与_Find_next()函数

程序员文章站 2022-03-13 09:18:42
bitset中_Find_first()与_Find_next()函数 很有趣~~但是没怎么有用~~的两个函数。 就是找到从低位到高位第一个1的位置 cpp include int main() { std::bitset B; B.set(2); B.set(4); B.set(233); std ......

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