15

I work almost exclusively in C++11/14, and usually cringe when I see code like this:

std::int64_t mArray;
mArray |= someMask << 1;

This is just an example; I'm talking about bit-wise manipulation in general. In C++, is there really any point? The above is mind-warping and error-prone, while using an std::bitset allows you to:

  1. more easily modify the size of the std::bitset as needed by adjusting a template parameter and letting the implementation take care of the rest, and
  2. spend less time figuring out what's going on (and possibly making mistakes) and write std::bitset in a manner similar to std::array or other data containers.

My question is; is there any reason not to use std::bitset over primitive types, other than for backward-compatability?

  • The size of a std::bitset is fixed at compile-time. That's the only crippling drawback I can think of. – rwong May 18 '15 at 1:48
  • 1
    @rwong I'm talking about std::bitset vs c-style bit manipulation (e.g. int), which is also fixed at compile-time. – quant May 18 '15 at 1:49
  • One reason could be legacy code: The code was written when std::bitset was not available (or known to the author) and there hasn't been a reason to rewrite the code to use std::bitset. – Bart van Ingen Schenau May 18 '15 at 5:14
  • I personally think the issue of how to make "operations on a set/map/array of binary variables" easy to understand to everyone is still largely unsolved, because there are many operations used in practice that cannot be reduced to simple operations. There are also too many ways to represent such sets, of which bitset is one, but a small vector or set of ints (of bit index) might also be legitimate. The philosophy of C/C++ does not hide these choice complexities from the programmer. – rwong May 18 '15 at 5:27
11

From a logical (non-technical) point of view, there is no advantage.

Any plain C / C++ code can be wrapped within suitable "library construct". After such wrapping, the matter of "whether this is more advantageous than that" becomes a moot question.

From a speed point-of-view, C / C++ should allow the library construct to generate code that is as efficient as the plain code that it wraps. This is however subject to:

  • Function inlining
  • Compile-time checking and elimination of unnecessary runtime checking
  • Dead code elimination
  • Many other code optimizations...

Using this kind of non-technical argument, any "missing functions" could be added by anyone, and therefore are not counted as disadvantage.

However, built-in requirements and limitations cannot be overcome with additional code. Below, I argue that the size of std::bitset is a compile-time constant, and therefore while not counted as disadvantage, it is still something that affects user's choice.


From an aesthetic point-of-view (readability, ease of maintenance etc), there is a difference.

However, it is not apparent that the std::bitset code immediately wins over the plain C code. One has to look at bigger pieces of code (and not some toy-sample) to say whether the use of std::bitset has improved the human quality of the source code.


The speed of bit manipulation depends on the coding style. Coding style affects both C/C++ bit manipulation, and is equally applicable to std::bitset as well, as explained follows.


If one writes code that uses the operator [] to read and write one bit at a time, one will have to do this multiple times if there are more than one bits to be manipulated. The same can be said of the C-style code.

However, bitset also has other operators, such as operator &=, operator <<=, etc., which operates on the full width of the bitset. Because the underlying machinery can often operate on 32-bit, 64-bit and sometimes 128-bit (with SIMD) at a time (in the same number of CPU cycles), code that is designed to take advantage of such multi-bit operations can be faster than "loopy" bit-manipulation code.

The general idea is called SWAR (SIMD within a register), and is a subtopic under bit manipulations.


Some C++ vendors might implement bitset between 64-bits and 128-bits with SIMD. Some vendors might not (but might eventually do). If there is a need to know what the C++ vendor's library is doing, the only way is to look at the disassembly.


As to whether std::bitset has limitations, I can give two examples.

  1. The size of std::bitset must be known at compile time. To make an array of bits with dynamically chosen size, one will have to use std::vector<bool>.
  2. The current C++ specification for std::bitset does not provide a way to extract a consecutive slice of N bits from a larger bitset of M bits.

The first one is fundamental, meaning that for people who need dynamically-sized bitsets, they must choose other options.

The second one can be overcome, because one can write some kind of adapters to perform the task, even if the standard bitset is not extensible.


There are certain types of advanced SWAR operations that are not provided out-of-the-box from std::bitset. One could read about these operations on this website about bit permutations. As usual, one can implement these on their own, operating on top of std::bitset.


Regarding the discussion on performance.

One admonition: a lot of people ask about why (something) from the standard library is much much slower than some simple C-style code. I would not repeat the prerequisite knowledge of microbenchmarking here, but I just have this advice: make sure to benchmark in "release mode" (with optimizations enabled), and make sure the code isn't being eliminated (dead code elimination) or being hoisted out of a loop (loop-invariant code motion).

Since in general we cannot tell whether someone (on the internet) were doing the microbenchmarks correctly, the only way we can get a reliable conclusion is to do our own microbenchmarks, and document the details, and submit to public review and critique. It doesn't hurt to re-do microbenchmarks that others have done before.

2

This certainly doesn't apply in all cases, but occasionally an algorithm might depend on the efficiency of C-style bit-twiddling to provide significant performance gains. The first example which comes to my mind is the use of bitboards, clever integer encodings of board game positions, to speed up chess engines and the like. Here, the fixed size of integer types is no problem, since chessboards are always 8*8 anyway.

For a simple example, consider the following function (taken from this answer by Ben Jackson) which tests a Connect Four position for victory:

// return whether newboard includes a win
bool haswon2(uint64_t newboard)
{
    uint64_t y = newboard & (newboard >> 6);
    uint64_t z = newboard & (newboard >> 7);
    uint64_t w = newboard & (newboard >> 8);
    uint64_t x = newboard & (newboard >> 1);
    return (y & (y >> 2 * 6)) | // check \ diagonal
           (z & (z >> 2 * 7)) | // check horizontal -
           (w & (w >> 2 * 8)) | // check / diagonal
           (x & (x >> 2));      // check vertical |
}
  • 2
    Do you think an std::bitset would be any slower? – quant May 18 '15 at 4:08
  • Well, from a quick glance at the source, the libc++ bitset is based on a single size_t or an array of them, so would probably compile down to something essentially equivalent/identical, especially on a system where sizeof(size_t) == 8 - so no, it probably wouldn't be any slower. – Ryan Pavlik Dec 2 '16 at 0:20

protected by gnat Mar 3 '17 at 22:43

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.