_Find_next() function in C++ bitset

Hello there! In this tutorial, you will learn about working of _Find_next() which is a built-in function of the bitset class. First, let us see what is a bitset.

A Bitset stores bits (elements with only two possible values 0 or 1). Syntax:

bitset<size> BS; // BS is the object

_Find_next() function

Let us take size = 16 for the object BS. Initially, all bits are 0 by default. So to set a bit:

BS[2] = 1;  // makes BS = 0000000000000100
BS[5] = BS[9] = 1; // makes BS = 0000001000100100

Here if we need to find the first set bit(1) we use _Find_first() function and to find the next set bit after any index we use _find_next() function. e.g.

cout<< BS._Find_first();  // prints 2 
cout<< BS._Find_next(4);  // prints 5
cout<< BS._Find_next(6);  // prints 9

If there isn’t any set bit after the provided index both the functions _Find_first() and _Find_next() will return the size of the object(here 16). The bitset has a time complexity of O(n/16) in the above case which makes it 16 times faster than bool array.

Here is a program to show their work:

#include <bits/stdc++.h>
using namespace std;

int main() {
  
  bitset<16> bs;
  bs[2] = bs[7] = bs[13] =1;

  cout<<"First set bit at: "<<bs._Find_first()<<endl;
  
  cout<<"All the remaining bits at: "<<endl;
  
  for(int i = bs._Find_first(); i < bs.size() ; i = bs._Find_next(i))
  {
      cout<< i <<" ";  
  }

  return 0;
}

Output:

First set bit at: 2
All the remaining bits at: 
2 7 13