22 General utilities library [utilities]

22.11 Bit manipulation [bit]

22.11.9 Permutation [bit.permute]

In the following descriptions,

(1.1)
let N denote the value of numeric_limits<T>::digits,
(1.2)
let $α_{n}$ denote the value of the $n^{th}$ least significant bit in the base-2 representation of an integer α, so that α equals $\sum_{n = 0}^{N - 1} α_{n} 2^{n}$ , and
(1.3)
let $σ (α, n) = \sum_{k = 0}^{n - 1} α_{k}$ be the count of one-bits among the lowest n bits of α.

template<class T>
  constexpr T bit_reverse(T x) noexcept;

Constraints: T is an unsigned integer type ([basic.fundamental]).

Returns: reverse(x), where reverse is given by Formula 22.1, and x is x.

\begin{matrix} r e v e r s e (x) = N - 1 \sum n = 0 x_{n} 2^{N - n - 1} \\ (22.1) \end{matrix}

[Note 1:

bit_reverse(bit_reverse(x)) equals x.

— end note]

🔗

template<class T>
  constexpr T bit_repeat(T x, int l);

Constraints: T is an unsigned integer type ([basic.fundamental]).

Preconditions: l is greater than zero.

Returns:

r e p e a t (x, l)

, where repeat is given by Formula 22.2, x is x, and l is l.

\begin{matrix} r e p e a t (x, l) = N - 1 \sum n = 0 x_{(n mod l)} 2^{n} \\ (22.2) \end{matrix}

Throws: Nothing.

Remarks: A function call expression that violates the precondition in the Preconditions: element is not a core constant expression ([expr.const.core]).

[Example 1:

bit_repeat(uint32_t{0xc}, 4) equals 0xcccccccc.

— end example]

🔗

template<class T>
  constexpr T bit_compress(T x, T m) noexcept;

Constraints: T is an unsigned integer type ([basic.fundamental]).

Returns:

c o m p r e s s (x, m)

, where compress is given by Formula 22.3, x is x, and m is m.

\begin{matrix} c o m p r e s s (x, m) = N - 1 \sum n = 0 m_{n} x_{n} 2^{σ (m, n)} \\ (22.3) \end{matrix}

[Example 2:

bit_compress(0bABCD, 0b0101) equals 0b00BD for any bits A, B, C, and D.

— end example]

🔗

template<class T>
  constexpr T bit_expand(T x, T m) noexcept;

Constraints: T is an unsigned integer type ([basic.fundamental]).

Returns:

e x p a n d (x, m)

, where expand is given by Formula 22.4, x is x, and m is m.

\begin{matrix} e x p a n d (x, m) = N - 1 \sum n = 0 m_{n} x_{σ (m, n)} 2^{n} \\ (22.4) \end{matrix}

[Example 3:

bit_expand(0bABCD, 0b0101) equals 0b0C0D for any bits A, B, C, and D.

— end example]