1. Introduction
[P0553R4] added the bit manipulation library to C++20, which introduced many useful utility functions.
Some of these already have a counterpart in
(such as
as
),
but not nearly all of them.
This leaves
overall lacking in functionality,
which is unfortunate because
is an undeniably useful container.
At the time of writing, it is used in 73K files on GitHub; see [GitHub1].
does not (and should not) expose the underlying integer sequence of the implementation.
Therefore, it is not possible for the user to implement these operations efficiently themselves.
2. Proposed changes
For each of the functions from the bit manipulation library that are not yet available
in
, add a member function.
Add a small amount of further useful member functions.
function
| Proposed member
|
---|---|
|
|
|
|
| |
|
|
| |
|
|
| |
|
|
| |
|
|
|
|
|
The additional overloads for the counting functions allow counting from a starting position. This can be useful for iterating over all set bits:
bitset < 128 > bits ; for ( size_t i = 0 ; i != 128 ; ++ i ) { i += bits . countr_zero ( i ); if ( i == 128 ) break ; // ... }
Note:
and
counterparts are not proposed, only functions solely
dedicated to the manipulation of bit sequences.
3. Design considerations
The naming of the member functions is based on the naming scheme in the
header.
3.1. reverse
is a notable exception, which does not yet exist in
.
This function is added because the method for reversing integers may be tremendously faster than
doing so bit by bit.
ARM has a dedicated
instruction for reversing bits, which could be leveraged.
I have written a not yet published proposal [Schultke1] which adds a corresponding bit-reversal function to
.
3.2. Counting overloads
,
,
, and
are overloaded member functions which take a
argument or nothing.
This is preferrable to a single member function with a defaulted argument because the overloads
have different
specifications.
The overloads which take no arguments have a wide constract and can be marked
,
whereas the overloads taking
may throw
.
4. Impact on existing code
The semantics of existing
member functions remain unchanged, and no existing valid code
is broken.
This proposal is purely an extension of the functionality of
.
5. Implementation experience
[Bontus1] provides a
implementation which supports most proposed features.
There are no obvious obstacles to implementing the new features in common standard library
implementations.
6. Proposed wording
The proposed changes are relative to the working draft of the standard as of [N4917].
Modify the header synopsis in subclause 17.3.2 [version.syn] as follows:
#define __cpp_lib_bitset 202306L 20XXXXL // also in <bitset>
Modify the header synopsis in subclause 22.9.2.1 [template.bitset.general] as follows:
namespace std { template < size_t N > class bitset { public : // bit reference [...] // [bitset.members], bitset operations constexpr bitset & operator &= ( const bitset & rhs ) noexcept ; constexpr bitset & operator |= ( const bitset & rhs ) noexcept ; constexpr bitset & operator ^= ( const bitset & rhs ) noexcept ; constexpr bitset & operator <<= ( size_t pos ) noexcept ; constexpr bitset & operator >>= ( size_t pos ) noexcept ; constexpr bitset operator << ( size_t pos ) const noexcept ; constexpr bitset operator >> ( size_t pos ) const noexcept ; + constexpr bitset & rotl ( size_t pos ) noexcept ; + constexpr bitset & rotr ( size_t pos ) noexcept ; + constexpr bitset & reverse () noexcept ; constexpr bitset & set () noexcept ; constexpr bitset & set ( size_t pos , bool val = true); constexpr bitset & reset () noexcept ; constexpr bitset & reset ( size_t pos ); constexpr bitset operator ~ () const noexcept ; constexpr bitset & flip () noexcept ; constexpr bitset & flip ( size_t pos ); // element access [...] // observers constexpr size_t count () const noexcept ; + constexpr size_t countl_zero () const noexcept ; + constexpr size_t countl_zero ( size_t pos ) const ; + constexpr size_t countl_one () const noexcept ; + constexpr size_t countl_one ( size_t pos ) const ; + constexpr size_t countr_zero () const noexcept ; + constexpr size_t countr_zero ( size_t pos ) const ; + constexpr size_t countr_one () const noexcept ; + constexpr size_t countr_one ( size_t pos ) const ; constexpr size_t size () const noexcept ; constexpr bool operator == ( const bitset & rhs ) const noexcept ; constexpr bool test ( size_t pos ) const ; constexpr bool all () const noexcept ; constexpr bool any () const noexcept ; constexpr bool none () const noexcept ; + constexpr bool one () const noexcept ; }; // [bitset.hash], hash support template < class T > struct hash ; template < size_t N > struct hash < bitset < N >> ; }
Modify subclause 22.9.2.3 [bitset.members] as follows:
constexpr bitset operator >> ( size_t pos ) const noexcept ; Returns:
.
bitset ( * this ) >>= pos
constexpr bitset & rotl ( size_t pos ) noexcept ; Effects: Replaces each bit at position
in
I with the bit at position
* this , where all arithmetic is performed using a hypothetical unsigned integer type which is at least one bit wider than
( N - pos % N + I ) % N .
size_t Returns:
.
* this
constexpr bitset & rotr ( size_t pos ) noexcept ; Effects: Replaces each bit at position
in
I with the bit at position
* this , where all arithmetic is performed using a hypothetical unsigned integer type which is at least one bit wider than
( pos + I ) % N .
size_t Returns:
.
* this
constexpr bitset & reverse () noexcept ; Effects: Replaces each bit at position
in
I with the bit at position
* this .
N - I - 1 Returns:
.
* this [...]
constexpr bitset & count () noexcept ; Returns: A count of the number of bits set in
.
* this
constexpr size_t countl_zero ( size_t pos ) const ; Returns: The number of consecutive zero-bits in
, starting at position
* this , and traversing
pos in decreasing position direction.
* this Throws:
if
out_of_range does not correspond to a valid bit position.
pos
constexpr size_t countl_zero () const noexcept ; Returns:
.
countl_zero ( N - 1 )
constexpr size_t countl_one ( size_t pos ) const ; Returns: The number of consecutive one-bits in
, starting at position
* this , and traversing
pos in decreasing position direction.
* this Throws:
if
out_of_range does not correspond to a valid bit position.
pos
constexpr size_t countl_one () const noexcept ; Returns:
.
countl_one ( N - 1 )
constexpr size_t countr_zero ( size_t pos ) const ; Returns: The number of consecutive zero-bits in
, starting at position
* this , and traversing
pos in increasing position direction.
* this Throws:
if
out_of_range does not correspond to a valid bit position.
pos
constexpr size_t countr_zero () const noexcept ; Returns:
.
countr_zero ( 0 )
constexpr size_t countr_one ( size_t pos ) const ; Returns: The number of consecutive one-bits in
, starting at position
* this , and traversing
pos in increasing position direction.
* this Throws:
if
out_of_range does not correspond to a valid bit position.
pos
constexpr size_t countr_one () const noexcept ; Returns:
.
countr_one ( 0 ) [...]
constexpr bool none () const noexcept ; Returns:
.
count () == 0
constexpr bool one () const noexcept ; Returns:
.
count () == 1
Note: The use of a hypothetical integer type in the specification of
and
is necessary
because
would be incorrect when
wraps.