Find the highest index set to true in std::bitset

user_1513286 0
Viewed 1969

I'm using std::bitset<9> deck in my program. By default it initializes all bits to 0.

Somewhere in my code I'm doing: deck.flip(index) where index can be any number from 0-8 (bitset indexes).

Now what I need is to find the index of the last bit set to true.

E.g:

000100010 - bitset
876543210 - index

In this example the latest bit set to true is at index 5. That is what I would like to find using std::bitset.

I have read the documentation https://en.cppreference.com/w/cpp/utility/bitset and found no useful function to do this, and as a beginner I'm having a hard time figuring out, how can I do this?

(Sorry if question is poorly written, english is my second language)

c++
2 Answers

It seems that only option is to iterate over bit set and find last bit set since bit set does not have support for iterators.

#include <iostream>
#include <bitset>
#include <optional>

template <size_t N>
constexpr std::optional<int> find_last_index_of_bit_set(std::bitset<N> set)
{
    for (int i = set.size()-1; i > -1; --i) {
      if (set.test(i)) {
          return std::optional(i);
      }
    }
    return std::nullopt;
}

int main() 
{
    std::bitset<10> bitSet("000100010");

    auto pos = find_last_index_of_bit_set(bitSet);

    if (pos.has_value()) {
        std::cout << "Max index is: " << pos.value() << '\n';
    } else {
        std::cout << "No bit set";
    }
}
Edin_490770

Here's a gcc/clang specific way using the __builtin_clzl() intrinsic, which returns the number of leading 0 bits starting from the most significant:

#include <bitset>
#include <cassert>
#include <climits>
#include <iostream>

template<std::size_t N>
int msb(const std::bitset<N> &bs) {
  static_assert(N <= (CHAR_BIT * sizeof(unsigned long)), "bitset is too big");
  auto n = bs.to_ulong();
  // C++20 will have std::countl_zero() but in the meantime:
  assert(n != 0); // clz is undefined if n is 0. Maybe return -1 in this case?
  return (CHAR_BIT * sizeof n) - __builtin_clzl(n) - 1;
}

int main() {
  std::bitset<9> bs;
  bs[1] = 1;
  bs[5] = 1;
  std::cout << "Highest set bit is " << msb(bs) << '\n';
  return 0;
}

will print Highest set bit is 5. This approach only works with bitsets equal or smaller than the number of bits in an unsigned long, of course (Though it can go up to unsigned long long with a few minor changes)

user_99521960
Related