std::bitset with constexpr implementations plus additional features.
Note |
---|
This version of bitset2 is for C++17. For C++14 checkout the corresponding branch. |
Bitset2::bitset2 is a header-only library. It provides the same functionality as std::bitset with the following extensions/changes.
Focus was set on having as many functions implemented as constexpr as possible. Moreover a second template parameter (with appropriate default) allows control of the underlying data structure (see below).
bitset2( std::array<T, N> const & )
, where T
needs not necessarily be equal to base_t
. T
has to be an unsigned integral type.bitset2( unsigned __int128 )
if supported by compiler.std::bitset
.~
, ==
, !=
, |
, &
, ^
, <<
(shift left), >>
(shift right), []
(bit access).<<=
, >>=
, |=
, &=
, ^=
test
, none
, any
, all
, count
, to_ulong
, to_ullong
.set
, reset
, and flip
.+
for adding two bitset2 objects.++
, --
, +=
.<
, >
, <=
, >=
.rotate_left
and rotate_right
for binary rotations.rotate_left
and rotate_right
.to_hex_string()
(see below).to_u128()
(if supported by the compiler) returning an unsigned __int128
value. Throws std::overflow_error
if the value doesn't fit into 128 bits.test_set( size_t bit, bool value= true )
, which sets or clears the specified bit and returns its previous state. Throws out_of_range
if bit >= N.difference
, which computes the set difference (bs1 & ~bs2
) of two bitset2 objects.difference
.find_first()
, find_last
, and find_next(size_t)
return the index of the first, last, or next bit set respectively. Returning npos
if all (remaining) bits are false.find_first_zero()
, find_last_zero
, and find_next_zero(size_t)
return the index of the first, last, or next bit unset respectively. Returning npos
if all (remaining) bits are true.has_single_bit
returning true if exactly one bit is set.complement2(bs)
computing the two's complement (~bs +1).complement2
.reverse
, which returns its argument with bits reversed.reverse
.midpoint(bs1,bs2,bool round_down=false)
returns half the sum of bs1 and bs2 without overflow. Like std::midpoint rounds towards bs1
if round_down==false
.convert_to<n>
for converting an m-bit bitset2 into an n-bit bitset2.convert_to<n,T>
for converting an m-bit bitset2 into an n-bit bitset2 with base_t=T
.data()
gives read access to the underlying array<base_t,N>
. Here element with an index zero is the least significant word.zip_fold_and
and zip_fold_or
. See below for details.#include <iostream>
#include <array>
#include <cassert>
#include "bitset2.hpp"
template<size_t n_bits>
using BS2= Bitset2::bitset2<n_bits>;
int main()
{
using bs_128= BS2<128>;
using base_t_128= bs_128::base_t;
constexpr std::array<base_t_128,2>
ar1{{ ~(base_t_128(0)), base_t_128(0xFEDCBA) }};
constexpr bs_128 b1{ ar1 };
constexpr auto b1_add= b1 + b1;
constexpr auto b1_shft= b1 << 1; // binary shift
static_assert( b1_add == b1_shft, "" );
std::cout << b1.to_hex_string() // 0000000000fedcbaffffffffffffffff
<< "\n"
<< b1_add.to_hex_string() // 0000000001fdb975fffffffffffffffe
<< "\n";
BS2<12> b2;
for( size_t c= 0; c < 12; c += 2 ) b2[c]= true;
auto b3= ~b2;
std::cout << b2 << "\n"; // 010101010101
std::cout << b2.flip() << "\n"; // 101010101010
assert( b2 == b3 );
BS2<7> const b4{ "1110000" };
auto const b5= Bitset2::rotate_left( b4, 3 );
std::cout << b4 << "\n" // 1110000
<< b5 << "\n"; // 0000111
BS2<7> b6{ "1010010" };
b6.reverse();
std::cout << b6 << "\n"; // 0100101
}
The following example illustrates how non-const constexpr operators and functions are useful for writing constexpr functions. It converts between Gray and binary encoding.
template<size_t N,class T>
constexpr
Bitset2::bitset2<N,T>
binary_to_gray( Bitset2::bitset2<N,T> const &bs )
{ return bs ^ (bs >> 1); }
template<size_t N,class T>
constexpr
Bitset2::bitset2<N,T>
gray_to_binary( Bitset2::bitset2<N,T> bs )
{
Bitset2::bitset2<N,T> mask= bs >> 1;
for( ; !mask.none(); mask >>= 1 ) bs ^= mask;
return bs;
} // gray_to_binary
int main()
{
using ULLONG= unsigned long long;
constexpr std::array<ULLONG,2> arr_01a{{ 0xFEFDFCFBFAF9F8F7ull, 1ull }};
constexpr Bitset2::bitset2<129> bs_01a{ arr_01a };
constexpr auto gray_01a= binary_to_gray( bs_01a );
constexpr auto bin_01a= gray_to_binary( gray_01a );
static_assert( bs_01a == bin_01a, "" );
}
bitset2
is declared as
template< size_t N, class T >
class bitset2;
N
is the number of bits and T
has to be an unsigned
integral type.
T
can be unsigned __int128
if supported by the compiler. Data
represented by bitset2
objects are stored in elements of type
std::array<T,n_array>
.
T
defaults
to uint8_t
, uint16_t
, or uint32_t
if N
bits fit into these integers
(and the type is supported by the system).
T
defaults to unsigned long long
otherwise. The following aliases and
constants are public within bitset2
:
using base_t= T;
size_t n_array;
Number of words in the underlying arrayusing array_t= std::array<T,n_array>;
Underlying data typeThe function to_hex_string
takes - as an optional argument - an element of type
hex_params
, which is defined as
template< class CharT = char,
class Traits = std::char_traits<CharT>,
class Allocator = std::allocator<CharT> >
struct hex_params
{
using str_t= std::basic_string<CharT,Traits,Allocator>;
CharT zeroCh= CharT( '0' );
CharT aCh= CharT( 'a' );
bool leadingZeroes= true;
bool nonEmpty= true;
str_t prefix;
};
It allows for fine-tuning the outcome of the function. In the following examples, the output is shown in the comments.
bitset2<16> b16_a( "0000101000011111" );
bitset2<16> b16_b;
std::cout
<< b16_a.to_hex_string() << '\n' // 0a1f
<< b16_a.to_hex_string( hex_params<>{'0', 'A', false, true, "0x"}) // 0xA1F
<< '\n'
<< b16_a.to_hex_string( {.aCh='A', .leadingZeroes=false, .prefix="0x"} ) // Same with C++-20
<< '\n'
<< b16_b.to_hex_string() << '\n' // 0000
<< b16_b.to_hex_string( hex_params<>{'0', 'a', false, false, "0X"}) // 0X
<< '\n'
<< b16_b.to_hex_string( {.leadingZeroes=false, .nonEmpty=false, .prefix="0X"} ) // Same with C++-20
<< '\n';
Functions zip_fold_and(bs1,bs2,f)
and zip_fold_or(bs1,bs2,f)
expect two
variables of type bitset2
and a functional object f
.
The latter must accept two variables of type base_t
and return a bool
.
zip_fold_*
are mapped over the underlying
std::array<base_t,n>
s. They will
short-circuit
if possible, which can result in performance advantages.
zip_fold_and
returns true
if f
returns true
for each pair of base_t
s, while zip_fold_or
returns true
if f
returns true
for at least one pair of base_t
s.
In other words zip_fold_and
and zip_fold_or
are similar to
std::inner_product(...,BinOp1 op1,BinOp2 op2)
with op1
set to &&
and ||
, resp.
For instance is_subset_of
as proposed in p0125r0
can be implemented as follows.
template<size_t N,class T>
constexpr
bool
is_subset_of( Bitset2::bitset2<N,T> const &bs1,
Bitset2::bitset2<N,T> const &bs2 ) noexcept
{
using base_t= T;
return Bitset2::zip_fold_and( bs1, bs2,
[]( base_t v1, base_t v2 ) noexcept
// Any bit unset in v2 must not be set in v1
{ return (v1 & ~v2) == 0; } );
}
constexpr Bitset2::bitset2<7> b7_a( 0b1000101ull );
constexpr Bitset2::bitset2<7> b7_b( 0b1010101ull );
static_assert( is_subset_of( b7_a, b7_b), "" );
Similarly, an unequal
function can be defined as
template<size_t N,class T>
bool
unequal( Bitset2::bitset2<N,T> const &bs1, Bitset2::bitset2<N,T> const &bs2 )
{
using base_t= T;
return Bitset2::zip_fold_or( bs1, bs2,
[]( base_t v1, base_t v2 ) noexcept
{ return v1 != v2; } );
}
The following code shows a counter based on a 128-bit integer. If the counter gets incremented once at each nanosecond, you have to wait for overflow for only 1.078 * 1022 years.
Bitset2::bitset2<128> c;
for( ;; ++c ) {}