501 lines
17 KiB
Markdown
501 lines
17 KiB
Markdown
[bit]
|
||
|
||
# 22 General utilities library [[utilities]](./#utilities)
|
||
|
||
## 22.11 Bit manipulation [bit]
|
||
|
||
### [22.11.1](#general) General [[bit.general]](bit.general)
|
||
|
||
[1](#general-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15628)
|
||
|
||
The header <bit> provides components to access,
|
||
manipulate and process both individual bits and bit sequences[.](#general-1.sentence-1)
|
||
|
||
### [22.11.2](#syn) Header <bit> synopsis [[bit.syn]](bit.syn)
|
||
|
||
// all freestandingnamespace std {// [[bit.cast]](#cast "22.11.3 Function template bit_cast"), bit_casttemplate<class To, class From>constexpr To bit_cast(const From& from) noexcept; // [[bit.byteswap]](#byteswap "22.11.4 byteswap"), byteswaptemplate<class T>constexpr T byteswap(T value) noexcept; // [[bit.pow.two]](#pow.two "22.11.5 Integral powers of 2"), integral powers of 2template<class T>constexpr bool has_single_bit(T x) noexcept; template<class T>constexpr T bit_ceil(T x); template<class T>constexpr T bit_floor(T x) noexcept; template<class T>constexpr int bit_width(T x) noexcept; // [[bit.rotate]](#rotate "22.11.6 Rotating"), rotatingtemplate<class T>constexpr T rotl(T x, int s) noexcept; template<class T>constexpr T rotr(T x, int s) noexcept; // [[bit.count]](#count "22.11.7 Counting"), countingtemplate<class T>constexpr int countl_zero(T x) noexcept; template<class T>constexpr int countl_one(T x) noexcept; template<class T>constexpr int countr_zero(T x) noexcept; template<class T>constexpr int countr_one(T x) noexcept; template<class T>constexpr int popcount(T x) noexcept; // [[bit.endian]](#endian "22.11.8 Endian"), endianenum class endian { little = *see below*,
|
||
big = *see below*,
|
||
native = *see below*};}
|
||
|
||
### [22.11.3](#cast) Function template bit_cast [[bit.cast]](bit.cast)
|
||
|
||
[ð](#lib:bit_cast)
|
||
|
||
`template<class To, class From>
|
||
constexpr To bit_cast(const From& from) noexcept;
|
||
`
|
||
|
||
[1](#cast-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15691)
|
||
|
||
*Constraints*:
|
||
|
||
- [(1.1)](#cast-1.1)
|
||
|
||
sizeof(To) == sizeof(From) is true;
|
||
|
||
- [(1.2)](#cast-1.2)
|
||
|
||
is_trivially_copyable_v<To> is true; and
|
||
|
||
- [(1.3)](#cast-1.3)
|
||
|
||
is_trivially_copyable_v<From> is true[.](#cast-1.sentence-1)
|
||
|
||
[2](#cast-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15699)
|
||
|
||
*Mandates*: Neither To nor From are consteval-only types ([[expr.const]](expr.const "7.7 Constant expressions"))[.](#cast-2.sentence-1)
|
||
|
||
[3](#cast-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15703)
|
||
|
||
*Constant When*: To, From, and the types of all subobjects
|
||
of To and From are types T such that:
|
||
|
||
- [(3.1)](#cast-3.1)
|
||
|
||
is_union_v<T> is false;
|
||
|
||
- [(3.2)](#cast-3.2)
|
||
|
||
is_pointer_v<T> is false;
|
||
|
||
- [(3.3)](#cast-3.3)
|
||
|
||
is_member_pointer_v<T> is false;
|
||
|
||
- [(3.4)](#cast-3.4)
|
||
|
||
is_volatile_v<T> is false; and
|
||
|
||
- [(3.5)](#cast-3.5)
|
||
|
||
T has no non-static data members of reference type[.](#cast-3.sentence-1)
|
||
|
||
[4](#cast-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15715)
|
||
|
||
*Returns*: An object of type To[.](#cast-4.sentence-1)
|
||
|
||
Implicitly creates objects nested within the result ([[intro.object]](intro.object "6.8.2 Object model"))[.](#cast-4.sentence-2)
|
||
|
||
Each bit of the value representation of the result
|
||
is equal to the corresponding bit in the object representation
|
||
of from[.](#cast-4.sentence-3)
|
||
|
||
Padding bits of the result are unspecified[.](#cast-4.sentence-4)
|
||
|
||
For the result and each object created within it,
|
||
if there is no value of the object's type corresponding to the
|
||
value representation produced, the behavior is undefined[.](#cast-4.sentence-5)
|
||
|
||
If there are multiple such values, which value is produced is unspecified[.](#cast-4.sentence-6)
|
||
|
||
A bit in the value representation of the result is indeterminate if
|
||
it does not correspond to a bit in the value representation of from or
|
||
corresponds to a bit
|
||
for which the smallest enclosing object is not within its lifetime or
|
||
has an indeterminate value ([[basic.indet]](basic.indet "6.8.5 Indeterminate and erroneous values"))[.](#cast-4.sentence-7)
|
||
|
||
A bit in the value representation of the result is erroneous
|
||
if it corresponds to a bit
|
||
for which the smallest enclosing object has an erroneous value[.](#cast-4.sentence-8)
|
||
|
||
For each bit b in the value representation of the result
|
||
that is indeterminate or erroneous,
|
||
let u be the smallest object containing that bit enclosing b:
|
||
|
||
- [(4.1)](#cast-4.1)
|
||
|
||
If u is of unsigned ordinary character type or std::byte type,u has an indeterminate value
|
||
if any of the bits in its value representation are indeterminate, or
|
||
otherwise has an erroneous value[.](#cast-4.1.sentence-1)
|
||
|
||
- [(4.2)](#cast-4.2)
|
||
|
||
Otherwise, if b is indeterminate, the behavior is undefined[.](#cast-4.2.sentence-1)
|
||
|
||
- [(4.3)](#cast-4.3)
|
||
|
||
Otherwise, the behavior is erroneous, and the result is as specified above[.](#cast-4.3.sentence-1)
|
||
|
||
The result does not otherwise contain any indeterminate or erroneous values[.](#cast-4.sentence-10)
|
||
|
||
### [22.11.4](#byteswap) byteswap [[bit.byteswap]](bit.byteswap)
|
||
|
||
[ð](#lib:byteswap)
|
||
|
||
`template<class T>
|
||
constexpr T byteswap(T value) noexcept;
|
||
`
|
||
|
||
[1](#byteswap-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15760)
|
||
|
||
*Constraints*: T models [integral](concepts.arithmetic#concept:integral "18.4.7 Arithmetic concepts [concepts.arithmetic]")[.](#byteswap-1.sentence-1)
|
||
|
||
[2](#byteswap-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15764)
|
||
|
||
*Mandates*: T does not have padding bits ([[basic.types.general]](basic.types.general "6.9.1 General"))[.](#byteswap-2.sentence-1)
|
||
|
||
[3](#byteswap-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15768)
|
||
|
||
Let the sequence R comprise
|
||
the bytes of the object representation of value in reverse order[.](#byteswap-3.sentence-1)
|
||
|
||
[4](#byteswap-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15772)
|
||
|
||
*Returns*: An object v of type T such that each byte in the object representation of v is equal to
|
||
the byte in the corresponding position in R[.](#byteswap-4.sentence-1)
|
||
|
||
### [22.11.5](#pow.two) Integral powers of 2 [[bit.pow.two]](bit.pow.two)
|
||
|
||
[ð](#lib:has_single_bit)
|
||
|
||
`template<class T>
|
||
constexpr bool has_single_bit(T x) noexcept;
|
||
`
|
||
|
||
[1](#pow.two-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15788)
|
||
|
||
*Constraints*: T is an unsigned integer type ([[basic.fundamental]](basic.fundamental "6.9.2 Fundamental types"))[.](#pow.two-1.sentence-1)
|
||
|
||
[2](#pow.two-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15792)
|
||
|
||
*Returns*: true if x is an integral power of two;false otherwise[.](#pow.two-2.sentence-1)
|
||
|
||
[ð](#lib:bit_ceil)
|
||
|
||
`template<class T>
|
||
constexpr T bit_ceil(T x);
|
||
`
|
||
|
||
[3](#pow.two-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15806)
|
||
|
||
Let N be the smallest power of 2 greater than or equal to x[.](#pow.two-3.sentence-1)
|
||
|
||
[4](#pow.two-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15809)
|
||
|
||
*Constraints*: T is an unsigned integer type ([[basic.fundamental]](basic.fundamental "6.9.2 Fundamental types"))[.](#pow.two-4.sentence-1)
|
||
|
||
[5](#pow.two-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15813)
|
||
|
||
*Preconditions*: N is representable as a value of type T[.](#pow.two-5.sentence-1)
|
||
|
||
[6](#pow.two-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15817)
|
||
|
||
*Returns*: N[.](#pow.two-6.sentence-1)
|
||
|
||
[7](#pow.two-7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15821)
|
||
|
||
*Throws*: Nothing[.](#pow.two-7.sentence-1)
|
||
|
||
[8](#pow.two-8)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15825)
|
||
|
||
*Remarks*: A function call expression
|
||
that violates the precondition in the *Preconditions*: element
|
||
is not a core constant expression ([[expr.const]](expr.const "7.7 Constant expressions"))[.](#pow.two-8.sentence-1)
|
||
|
||
[ð](#lib:bit_floor)
|
||
|
||
`template<class T>
|
||
constexpr T bit_floor(T x) noexcept;
|
||
`
|
||
|
||
[9](#pow.two-9)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15839)
|
||
|
||
*Constraints*: T is an unsigned integer type ([[basic.fundamental]](basic.fundamental "6.9.2 Fundamental types"))[.](#pow.two-9.sentence-1)
|
||
|
||
[10](#pow.two-10)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15843)
|
||
|
||
*Returns*: If x == 0, 0;
|
||
otherwise the maximal value y such that has_single_bit(y) is true and y <= x[.](#pow.two-10.sentence-1)
|
||
|
||
[ð](#lib:bit_width)
|
||
|
||
`template<class T>
|
||
constexpr int bit_width(T x) noexcept;
|
||
`
|
||
|
||
[11](#pow.two-11)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15858)
|
||
|
||
*Constraints*: T is an unsigned integer type ([[basic.fundamental]](basic.fundamental "6.9.2 Fundamental types"))[.](#pow.two-11.sentence-1)
|
||
|
||
[12](#pow.two-12)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15862)
|
||
|
||
*Returns*: If x == 0, 0;
|
||
otherwise one plus the base-2 logarithm of x,
|
||
with any fractional part discarded[.](#pow.two-12.sentence-1)
|
||
|
||
### [22.11.6](#rotate) Rotating [[bit.rotate]](bit.rotate)
|
||
|
||
[1](#rotate-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15872)
|
||
|
||
In the following descriptions,
|
||
let N denote numeric_limits<T>::digits[.](#rotate-1.sentence-1)
|
||
|
||
[ð](#rotate-itemdecl:1)
|
||
|
||
`template<class T>
|
||
constexpr T rotl(T x, int s) noexcept;
|
||
`
|
||
|
||
[2](#rotate-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15883)
|
||
|
||
*Constraints*: T is an unsigned integer type ([[basic.fundamental]](basic.fundamental "6.9.2 Fundamental types"))[.](#rotate-2.sentence-1)
|
||
|
||
[3](#rotate-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15887)
|
||
|
||
Let r be s % N[.](#rotate-3.sentence-1)
|
||
|
||
[4](#rotate-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15890)
|
||
|
||
*Returns*: If r is 0, x;
|
||
if r is positive, (x << r) | (x >> (N - r));
|
||
if r is negative, rotr(x, -r)[.](#rotate-4.sentence-1)
|
||
|
||
[ð](#rotate-itemdecl:2)
|
||
|
||
`template<class T>
|
||
constexpr T rotr(T x, int s) noexcept;
|
||
`
|
||
|
||
[5](#rotate-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15904)
|
||
|
||
*Constraints*: T is an unsigned integer type ([[basic.fundamental]](basic.fundamental "6.9.2 Fundamental types"))[.](#rotate-5.sentence-1)
|
||
|
||
[6](#rotate-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15908)
|
||
|
||
Let r be s % N[.](#rotate-6.sentence-1)
|
||
|
||
[7](#rotate-7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15911)
|
||
|
||
*Returns*: If r is 0, x;
|
||
if r is positive, (x >> r) | (x << (N - r));
|
||
if r is negative, rotl(x, -r)[.](#rotate-7.sentence-1)
|
||
|
||
### [22.11.7](#count) Counting [[bit.count]](bit.count)
|
||
|
||
[1](#count-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15920)
|
||
|
||
In the following descriptions,
|
||
let N denote numeric_limits<T>::digits[.](#count-1.sentence-1)
|
||
|
||
[ð](#count-itemdecl:1)
|
||
|
||
`template<class T>
|
||
constexpr int countl_zero(T x) noexcept;
|
||
`
|
||
|
||
[2](#count-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15931)
|
||
|
||
*Constraints*: T is an unsigned integer type ([[basic.fundamental]](basic.fundamental "6.9.2 Fundamental types"))[.](#count-2.sentence-1)
|
||
|
||
[3](#count-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15935)
|
||
|
||
*Returns*: The number of consecutive 0 bits in the value of x,
|
||
starting from the most significant bit[.](#count-3.sentence-1)
|
||
|
||
[*Note [1](#count-note-1)*:
|
||
|
||
Returns N if x == 0[.](#count-3.sentence-2)
|
||
|
||
â *end note*]
|
||
|
||
[ð](#count-itemdecl:2)
|
||
|
||
`template<class T>
|
||
constexpr int countl_one(T x) noexcept;
|
||
`
|
||
|
||
[4](#count-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15951)
|
||
|
||
*Constraints*: T is an unsigned integer type ([[basic.fundamental]](basic.fundamental "6.9.2 Fundamental types"))[.](#count-4.sentence-1)
|
||
|
||
[5](#count-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15955)
|
||
|
||
*Returns*: The number of consecutive 1 bits in the value of x,
|
||
starting from the most significant bit[.](#count-5.sentence-1)
|
||
|
||
[*Note [2](#count-note-2)*:
|
||
|
||
Returns N if x == numeric_limits<T>::max()[.](#count-5.sentence-2)
|
||
|
||
â *end note*]
|
||
|
||
[ð](#count-itemdecl:3)
|
||
|
||
`template<class T>
|
||
constexpr int countr_zero(T x) noexcept;
|
||
`
|
||
|
||
[6](#count-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15971)
|
||
|
||
*Constraints*: T is an unsigned integer type ([[basic.fundamental]](basic.fundamental "6.9.2 Fundamental types"))[.](#count-6.sentence-1)
|
||
|
||
[7](#count-7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15975)
|
||
|
||
*Returns*: The number of consecutive 0 bits in the value of x,
|
||
starting from the least significant bit[.](#count-7.sentence-1)
|
||
|
||
[*Note [3](#count-note-3)*:
|
||
|
||
Returns N if x == 0[.](#count-7.sentence-2)
|
||
|
||
â *end note*]
|
||
|
||
[ð](#count-itemdecl:4)
|
||
|
||
`template<class T>
|
||
constexpr int countr_one(T x) noexcept;
|
||
`
|
||
|
||
[8](#count-8)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15991)
|
||
|
||
*Constraints*: T is an unsigned integer type ([[basic.fundamental]](basic.fundamental "6.9.2 Fundamental types"))[.](#count-8.sentence-1)
|
||
|
||
[9](#count-9)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15995)
|
||
|
||
*Returns*: The number of consecutive 1 bits in the value of x,
|
||
starting from the least significant bit[.](#count-9.sentence-1)
|
||
|
||
[*Note [4](#count-note-4)*:
|
||
|
||
Returns N if x == numeric_limits<T>::max()[.](#count-9.sentence-2)
|
||
|
||
â *end note*]
|
||
|
||
[ð](#count-itemdecl:5)
|
||
|
||
`template<class T>
|
||
constexpr int popcount(T x) noexcept;
|
||
`
|
||
|
||
[10](#count-10)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L16011)
|
||
|
||
*Constraints*: T is an unsigned integer type ([[basic.fundamental]](basic.fundamental "6.9.2 Fundamental types"))[.](#count-10.sentence-1)
|
||
|
||
[11](#count-11)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L16015)
|
||
|
||
*Returns*: The number of 1 bits in the value of x[.](#count-11.sentence-1)
|
||
|
||
### [22.11.8](#endian) Endian [[bit.endian]](bit.endian)
|
||
|
||
[1](#endian-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L16022)
|
||
|
||
Two common methods of byte ordering in multibyte scalar types are big-endian
|
||
and little-endian in the execution environment[.](#endian-1.sentence-1)
|
||
|
||
Big-endian is a format for
|
||
storage of binary data in which the most significant byte is placed first,
|
||
with the rest in descending order[.](#endian-1.sentence-2)
|
||
|
||
Little-endian is a format for storage of
|
||
binary data in which the least significant byte is placed first, with the rest
|
||
in ascending order[.](#endian-1.sentence-3)
|
||
|
||
This subclause describes the endianness of the scalar types
|
||
of the execution environment[.](#endian-1.sentence-4)
|
||
|
||
[ð](#lib:endian)
|
||
|
||
`enum class endian {
|
||
little = see below,
|
||
big = see below,
|
||
native = see below
|
||
};
|
||
`
|
||
|
||
[2](#endian-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L16044)
|
||
|
||
If all scalar types have size 1 byte, then all of endian::little,endian::big, and endian::native have the same value[.](#endian-2.sentence-1)
|
||
|
||
Otherwise, endian::little is not equal to endian::big[.](#endian-2.sentence-2)
|
||
|
||
If all scalar types are big-endian, endian::native is
|
||
equal to endian::big[.](#endian-2.sentence-3)
|
||
|
||
If all scalar types are little-endian, endian::native is
|
||
equal to endian::little[.](#endian-2.sentence-4)
|
||
|
||
Otherwise, endian::native is not equal
|
||
to either endian::big or endian::little[.](#endian-2.sentence-5)
|