6

I would like to use the std::bitset::all but unfortunately my compiler is pre-dated C++11. I know that I could mimicate the functionality by checking in a loop whether all bits of my std::bitset are set.

e.g.,

template<std::size_t N>
bool
all(std::bitset<N> const &bs) {
  int hits(0), sz(bs.size());
  for(int i(0); i < sz; ++i) {
    hits += bs[i];
  }
  return hits == sz;
}

Q:

Is there a more proper implementation of a std::bitset::all substitute for pre-dated C++11 compilers than the one displayed above.

Jarod42
  • 203,559
  • 14
  • 181
  • 302
101010
  • 41,839
  • 11
  • 94
  • 168

5 Answers5

7

Just check if the count is equal to size:

template<size_t N>
bool all_set(const std::bitset<N>& b) {
    return b.count() == b.size();
}
Rapptz
  • 20,807
  • 5
  • 72
  • 86
5

If you want to avoid a loop, but don't care about maximum performace, you could compare count against size (i.e. check if the number of bits set equals the number of bits):

template<std::size_t N>
bool all(std::bitset<N> const &bs) {
    return bs.count() == bs.size();
}

The downside (but that's the same with other non-loop solutions as well as your implementation with a loop) is that it won't stop early at the first bit not being set. If you'd like to take advantage of that, modify your loop to exit early (and by the way, you don't need sz as it is N):

template<std::size_t N>
bool all(std::bitset<N> const &bs) {
    for (int i = 0; i < N; ++i)
        if (!bs[i]) return false;
    return true;
}
leemes
  • 44,967
  • 21
  • 135
  • 183
  • Since `size()` is O(1) and both `all()` and `count()` are O(n), I'd say your original solution is in the same big-Oh class as `all()` – Bulletmagnet Nov 13 '14 at 13:50
  • @Bulletmagnet Of course both are linear in N, that's the big-Oh. But if you care about maximum performance (which I usually don't, but looking at a lot of Stack Overflow questions most people seem to do), you shouldn't only look at big-Oh but also at constant factors or special cases. And if you exit early, you optimize for cases which have non-set bits near the beginning. It might be slower though, since it introduces a conditional branch (which is easily predictable to be fair). You can discuss a lot here but that's all premature optimization which I consider bad. I just gave an alternative. – leemes Nov 13 '14 at 13:53
  • 1
    Note also that most of bitset's O(n) methods (`count()`, `all()`, `none()`, `any()` ...) work on `unsigned long`s at a time. This means that `count() == `size()` might actually be faster than calling `operator[]` in a loop. – Bulletmagnet Nov 13 '14 at 14:02
  • 1
    Another downside to the early-exit one is that it becomes nearly impossible to vectorize. A well written `count` could add up 128 bits or more at a time. – Yakk - Adam Nevraumont Nov 13 '14 at 14:10
  • @Yakk I know, that's why I said "optimize for cases which have non-set bits near the beginning". You make the worst case much worse. But I'd like to emphasize again: that's all premature optimization, and I'm an enemy of that. I write concise code, and optimize only when I identified a bottleneck. – leemes Nov 13 '14 at 14:36
2

A silly way would be

(~bs).none();

(silly because operator~ returns a temporary).

Bulletmagnet
  • 5,665
  • 2
  • 26
  • 56
  • Silly because it does unnecessary work: it creates another bitset object, calls a method on it, then throws the new object away. I believe it's a premature pessimization :) – Bulletmagnet Nov 13 '14 at 16:12
2

You could use bs.count() == bs.size().

Sebastian Redl
  • 69,373
  • 8
  • 123
  • 157
1

Another way would be to use template metaprogramming and unroll the bits of the bitfield like the example below:

template<std::size_t N, int M>
struct bitset_all_helper {
  static bool check(std::bitset<N> const &bs) { return bs[M] && bitset_all_helper<N, M - 1>::check(bs); }
};

template<std::size_t N>
struct bitset_all_helper<N, 0> {
  static bool check(std::bitset<N> const &bs) { return bs[0]; }
};

template<std::size_t N>
bool bitset_all(std::bitset<N> const &bs) { return bitset_all_helper<N, N - 1>::check(bs); }

LIVE DEMO

101010
  • 41,839
  • 11
  • 94
  • 168
  • That's almost the same than simply writing a usual for-loop. The compiler is smart enough to unroll it for you, no ugly meta-programming required (not that I dislike meta-programming, but here it is simply not necessary). – leemes Nov 13 '14 at 15:59
  • In my experience, compilers are pretty conservative in unrolling. This solution almost forces the compiler to unroll (it actually "asks" it to inline, which I guess no compiler would refuse). – anatolyg Nov 13 '14 at 16:13