How to Increment a Dynamic Bitset with the STL
While working on a project involving bitsets, I had to implement a function that adds 1 to a binary number represented by a bitstet. In this article, we will compare how to implement such a function by using a for loop VS using STL algorithms.
C++ has two types of bitsets. The first type are static bitsets. Their size is known at compile tyme, and they’re implemented with std::bitset.
The second type are dynamic bitsets, of which the size is determined at runtime. One possible implementation is std::deque<bool>, because std::vector<bool> has issues (to read more about those issues, check out item 18 of Effective STL).
Here we focus on incrementing a dynamic bitset represented by a std::deque<bool>.
Incrementing a binary number
Before getting into the implementation itself, let’s see how to increment a binary number in the first place.
The logic is the following:
- if the rightmost bit is a 0, then we flip it and we’re done.
- if the rightmost bit is a 1, we flip it, and examine the second rightmost bit:
- if the second rightmost bit is 0, then we also flip it and we’re done.
- if the second rightmost bit is 1, then we flip it, and examine the third rightmost bit:
- …and so on.
And if all bits are 1, we will just reset them all to 0.
An implementation using a for loop
Another way to express this logic is that we flip all bits starting from the right, until we encouter a bit to 0. We then flip it and stop.
A direct translation of the above sentence into code would look like this:
void increment_for_loop(std::deque<bool>& bits)
{
for (auto bit = rbegin(bits); bit != rend(bits); ++bit)
{
flip(*bit);
if (*bit == true)
{
break;
}
}
}
rbegin and rend produce reverse iterators. They are iterators that allow to traverse an STL container from its last element all the way back to its first one. Just like the end iterator of a container points to one position past the last element, its rend points to one position before the first one.
Note that we have encapsulated the logic of flipping a bit into a separate function:
void flip(bool& bit)
{
bit = !bit;
}
Indeed, even if its implementation is very simple, I think that reading and understanding the word flip from client code takes less time than the expression bit = !bit.
We now have a piece of code that increments our dynamic bitset with the help of a for loop. But the good practice for manipulating collections in C++ is to use STL algorithms. Let’s see how to refactor this code so that it uses them.
An implementation using STL algorithms
Another way to see the logic is that we need to flip all the bits from the right end back to the last 0 of the bitset, included.
A first (incorrect) attempt of translating the above sentence could look like this:
void increment_STL(std::deque<bool>& bits)
{
auto lastFalse = std::find(rbegin(bits), rend(bits), false);
std::for_each(rbegin(bits), lastFalse, flip);
}
This code locates the last bit at 0 and flips the bits on its right. The problem is that it doesn’t flip the last bit at 0 itself.
The problem here is that STL doesn’t work smoothly with inclusive ranges: once we have located the position of the bit at 0, we can easily build a range excluding it, as in the above code. But to include it, we need to shift the iterator of one position:
void increment_STL(std::deque<bool>& bits)
{
auto lastFalse = std::find(rbegin(bits), rend(bits), false);
auto lastToFlip = std::next(lastFalse);
std::for_each(rbegin(bits), lastToFlip, flip);
}
But this introduces a new problem: what if the bits in the bitset are all set to 1? then lastFalse is rend(bits), and using std::next(rend(bits)) as the end of a range in for_each will read past the rend of the bitset. This would cause undefined behaviour.
We therefore need to accomodate for this case:
void increment_STL(std::deque<bool>& bits)
{
auto lastFalse = std::find(rbegin(bits), rend(bits), false);
auto lastToFlip = lastFalse == rend(bits) ? rend(bits) : std::next(lastFalse);
std::for_each(rbegin(bits), lastToFlip, flip);
}
Which code is better?
Here is all the code put together in a test program, with the two implementations:
#include <algorithm>
#include <deque>
#include <iostream>
void flip(bool& bit)
{
bit = !bit;
}
void increment_for_loop(std::deque<bool>& bits)
{
for (auto bit = rbegin(bits); bit != rend(bits); ++bit)
{
flip(*bit);
if (*bit == true)
{
break;
}
}
}
void increment_STL(std::deque<bool>& bits)
{
auto lastFalse = std::find(rbegin(bits), rend(bits), false);
auto lastToFlip = lastFalse == rend(bits) ? rend(bits) : std::next(lastFalse);
std::for_each(rbegin(bits), lastToFlip, flip);
}
int main()
{
auto number = std::deque<bool>(3);
for (int i = 0; i < 8; ++i)
{
increment_for_loop(number);
std::cout << number[0] << number[1] << number[2] << '\n';
}
}
The code using the for loop has the drawback of making its reader execute it mentally. This has a risk of wasting some time and energy at best, and understanding it incorrectly at worst. Our human brains are nowhere as good as computers to run for loops. Also, the for loop could evolve in a disorderly manner. We could be tempted to stick something in its conditional, or in the rest of the loop body, thus making it more complex.
The solution using the STL, on the other hand, probably offers more control over its future evolution. Since it’s not just one big loop, I find that making a structural change carries more incentive to think about using other algorithms.
However, the STL solution also has its drawbacks. It suffers from the complexity coming from its second line:
auto lastToFlip = lastFalse == rend(bits) ? rend(bits) : std::next(lastFalse);
This also takes some time to read and understand.
Overall, which solution do you think is better? Do you see another way to use the STL to write a more expressive implementation?
You may also like
Don't want to miss out ? Follow:
Share this post!
