CODEWITHSUNDEEP
c++
Vinícius
Vinícius

Reputation: 15746

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

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)

Upvotes: 7

Views: 4433

Answers (4)

Pratham Asrani
Pratham Asrani

Reputation: 1

#include <bits/stdc++.h>

using namespace std;

int setSetBit(int x, int y){

    bitset<32> _x(x);
    bitset<32> _y(y);
    string __x = _x.to_string();
    string __y = _y.to_string();
    __x.erase(0, __x.find('1'));
    __y.erase(0, __y.find('1'));
    cout << __x << ": " << __x.length() << " \n" << __y << ": "<< __y.length() << "\n";
}   

int main(){
    setSetBit(44, 3);
}

Output:

101100: 6 11: 2

Upvotes: 0

MDH
MDH

Reputation: 61

<bitset> has nothing built in for this, but in C++20 you can reduce the problem to one for <bit>.

#include <bit>
#include <bitset>
#include <iostream>
#include <limits>

// count leading zeroes in bitset<N>
template <size_t N> inline constexpr size_t countl_zero(std::bitset<N> x) {
  using bitsetN = std::bitset<N>;
  using ulong = unsigned long;
  using ullong = unsigned long long;
  constexpr size_t ulong_digits = std::numeric_limits<ulong>::digits;
  constexpr size_t ullong_digits = std::numeric_limits<ullong>::digits;

  // binary reduce until we have something <bit> can handle.
  size_t l_zero = 0;
  size_t digits = N;
  while (digits > ullong_digits) {
    const size_t half = digits / 2;
    const bitsetN high_bits = ~bitsetN(0) << half;
    if ((x & high_bits).any())
      x >>= half;
    else
      l_zero += half;
    digits -= half;
  }

  return digits > ulong_digits ? l_zero + std::countl_zero(x.to_ullong()) -
                                     (ullong_digits - digits)
                               : l_zero + std::countl_zero(x.to_ulong()) -
                                     (ulong_digits - digits);
}

template <size_t N> inline constexpr size_t bit_width(std::bitset<N> x) {
  return N - countl_zero(x);
}

int main(void) {
  constexpr size_t N = 9;
  using bitsetN = std::bitset<N>;
  {
    bitsetN bs("0");
    std::cout << bs << ":" << bit_width(bs) << std::endl;
  }
  {
    bitsetN bs("1");
    std::cout << bs << ":" << bit_width(bs) << std::endl;
  }
  {
    bitsetN bs("11");
    std::cout << bs << ":" << bit_width(bs) << std::endl;
  }
  {
    bitsetN bs("10000");
    std::cout << bs << ":" << bit_width(bs) << std::endl;
  }
  {
    bitsetN bs("101010000");
    std::cout << bs << ":" << bit_width(bs) << std::endl;
  }
}

output:

000000000:0
000000001:1
000000011:2
000010000:5
101010000:9

Upvotes: 2

Shawn
Shawn

Reputation: 52449

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)

Upvotes: 3

Edin Omeragic
Edin Omeragic

Reputation: 1968

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";
    }
}

Upvotes: 2

Related Questions