5

I am looking for a C++ bitset implementation that can answer if a bit is set in a range. std::bitset, vector, and boost::dynamic_bitset all give access to individual bits that I can loop over, but that isn't the most efficient way to query a range of bits to ask if any bit is set- I don't even need to know which one.

bitset b;
if(b.any(33, 199))
{
    // ...
}

Is there a library that provides this? I would like to run some benchmarks against other implementations (including one I may have to write), but I can't find any that appear to implement this functionality.

Ciro Santilli OurBigBook.com
  • 347,512
  • 102
  • 1,199
  • 985
JaredC
  • 5,150
  • 1
  • 20
  • 45
  • Much more effocient is not to try use container but use Hamming code/popcount algorithms or intrinstic function. Most of bitsets don't use binary representation internally because they weren't meants for fast bit operations with data. – Swift - Friday Pie Jan 06 '21 at 08:12

3 Answers3

1

Unfortunately in C++11 bitset it is not possible to set a range of bits to the given value by just specifying the boundaries of the range. Iterating over individual bits seems the most we can do. It is also not possible to check if all bits inside the range are set to the same value (1,0).

There is an open source project in Git that provides an alternative implementation of the BitSet (RangedBitset) that supports these operations. It uses an array of uint_64t_ words of any size internally, but can also handle ranges specified with the accuracy of the single bit. There you can do the things like

 a.set(4, 8, true); // set the range [ 4 .. 8 [ to true
 bool is_all_range = a.check(2, 6, true); // check if all range is set to 1.
Audrius Meškauskas
  • 20,936
  • 12
  • 75
  • 93
0

To check if some bit is set in the range [x,y] in bitset, you can use bs._Find_next(x-1). It returns the next set bit after the position x-1. Then you can check if the returned value is <=y or not.

bool Find_if_bitset_has_any_set_bit_in_range(bitset<M> &bs, int x, int y){
   if(bs._Find_next(x-1)<=y)   return 1;   //TRUE
   return 0;                               //FALSE
}
R Chinmay
  • 9
  • 1
  • 1
    `_Find_next` isn't in C++ standard https://en.cppreference.com/w/cpp/utility/bitset – phuclv Jan 06 '21 at 08:24
  • It works with ``#include `` on my PC. I am not very sure which specific standard C++ library is it associated to. You can refer this for more information on its implementation. [link](https://gcc.gnu.org/onlinedocs/gcc-4.6.2/libstdc++/api/a00775_source.html) – R Chinmay Jan 07 '21 at 07:14
  • [`_` followed by an uppercase character are reserved names](https://stackoverflow.com/q/228783/995714), which means this is some **extension** in some C++ STL implementations like libstdc++ but it's not standard C++ where STL names are always in lowercase. Did you see the link above? It's clear that that method isn't available in any C++ versions – phuclv Jan 07 '21 at 07:42
  • 1
    And it's in ``, not ``. See [Why should I not #include ``?](https://stackoverflow.com/q/31816095/995714) . See also [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/q/1452721/995714) – phuclv Jan 07 '21 at 07:45
-1

C++11's bitset provides the any() method that you are after, but if that isn't an option then just use b.to_ulong() and check for non zero.

Duncan Smith
  • 530
  • 2
  • 10
  • Can you provide a link? I see an `any()` in the reference, but not one based on a range of bits. – JaredC Oct 10 '13 at 13:04
  • 1
    std::bitset::any(): http://en.cppreference.com/w/cpp/utility/bitset/all_any_none, you are using C++11, right? – Duncan Smith Oct 10 '13 at 15:17
  • I can use c++11, but I don't think the `any()` you linked to supports **ranges**. I.e. it cannot answer the question "is any bit in the range [x,y] set?". – JaredC Oct 10 '13 at 15:34