Jens Maurer <Jens.Maurer@gmx.net>

Target audience: SG6, LEWG

2017-02-05

This paper proposes to add simple free functions for operations related to integral powers of 2 on all unsigned integer types.

A previous proposal was in "N3864: A constexpr bitwise operations library for C++" by Matthew Fioravante.

The foundation for digital computers are binary digits (also called "bits"), and as such operating with a base-2 representation of data is often most natural or most efficient.

It is expected that the functions provided with this proposal will be,
at some later time, overloaded for `std::datapar`

, the
nascent SIMD data type (see P0214R2: "Data-Parallel Vector Types &
Operations" by Matthias Kretz).

This proposal uses readable English names for the operations, using
the established abbreviations `pow`

and `ceil`

.

It is conceivable to add these functions to the
header `<cstdlib>`

(`abs`

and `div`

are already there), although a new header such as `<pow2>`

seems more
focused. The wording below adds a new header.

Per prevailing LWG convention, only those functions are marked
`noexcept`

that have a wide constract, i.e. no restrictions
on the values of the function arguments.

All functions are mathematically pure, i.e. do not access or modify
data other than the argument values, and thus are
marked `constexpr`

.

- Should the functions also be available for signed T? The proposed functions are not defined for negative values, but some programmers like to deal in signed ints.
- Should the result be unspecified instead of undefined behavior (implied by "Requires" clauses) if the argument is outside of the domain?
- Should log2(0) return -1? (Peter Dimov) This result naturally falls out from the obvious bit-level implementation. This requires that log(T) returns "int" (or similar) for built-in T (even unsigned T), but widens the contract for log2(T) so that it can be noexcept for unsigned T.

`<pow2>`

to the table in 17.5.1.2 [headers].
Append a new subsection to clause 26 [numerics] with the following content:

## 26.10 Integral powers of 2 [numeric.pow.two]

## 26.10.1 Header

`<pow2>`

synopsis [pow2.syn]namespace std { template <class T> constexpr bool ispow2(T x) noexcept; template <class T> constexpr T ceilpow2(T x); template <class T> constexpr T floorpow2(T x) noexcept; template <class T> constexpr T log2(T x); }## 26.10.1 Operations [numerics.pow.two.ops]

template <class T> constexpr bool ispow2(T x) noexcept;Returns:`true`

if x is a power of two.

Remarks:Participates in overload resolution only if T is an unsigned integer type (3.9.1 [basic.fundamental]).template <class T> constexpr T ceilpow2(T x);Requires:A value y representable as a value of type T exists where`ispow2(y)`

and`y >= x`

.

Returns:The minimal value`y`

such that`ispow2(y)`

and`y >= x`

.

Throws:Nothing.

Remarks:Participates in overload resolution only if T is an unsigned integer type (3.9.1 [basic.fundamental]).template <class T> constexpr T floorpow2(T x) noexcept;Returns:For`x == 0`

, 0; otherwise the maximal value`y`

such that`ispow2(y)`

and`y <= x`

.

Remarks:Participates in overload resolution only if T is an unsigned integer type (3.9.1 [basic.fundamental]).template <class T> constexpr T log2(T x);Requires:x > 0

Returns:The base-2 logarithm of x, with any fractional part discarded.

Throws:Nothing.

Remarks:Participates in overload resolution only if T is an unsigned integer type (3.9.1 [basic.fundamental]).

- ISO/IEC JTC1 SC22 WG21 N3864: "A constexpr bitwise operations library for C++" by Matthew Fioravante
- ISO/IEC JTC1 SC22 WG21 P0214R2: "Data-Parallel Vector Types & Operations" by Matthias Kretz
- ARM Compiler User Guide [large PDF]
- Intel x86 Instruction Set Reference [large PDF]
- PowerPC Architecture Book, Version 2.02: Book I: PowerPC User Instruction Set Architecture [large PDF inside ZIP]