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