C++ Logo


Advanced search

[std-proposals] [bitset] find first set bit after a position pos

From: Madhur Chauhan <madhur4127_at_[hidden]>
Date: Mon, 24 Oct 2022 20:49:44 +0530
Hello everybody,

*Problem*: Find the first set bit in a bitset with index >= a given pos
*Current Solution*: Run a simple loop over bits.
*Preferred solution*: Run a loop *over words *instead of bits. libstdc++
implements this extension as _Find_next() [1].

*Preferred solution* is 90x faster [2] than its counterpart. Due of lack of
standard functionality users have to either use pick a horribly slow
solution or hope for vendor's extension.

*Proposal*: Add a new member into std::bitset, which can be naively written

constexpr std::size_t find_first_set(std::size_t pos = 0) const {
  if (pos >= size()) {
    throw std::out_of_range("pos >= size");
  for (; pos < size(); ++pos) {
    if ((*this)[pos])
  return pos;

PS: libstdc++ has _Find_next(std::size_t pos) and _Find_first() but this
proposal combines both of them into a single function.

2. https://quick-bench.com/q/Vvl3-Pv2VMe12jOLtlEpbKfutCM

Madhur Chauhan
*“To live is the rarest thing in the world. Most people exist, that is
*- **Oscar Wilde*

Received on 2022-10-24 15:20:22