P0556R0: Integral power-of-2 operations

Introduction

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).

Design considerations

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.

Open issues

• 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.

Wording

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]).

References

• 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]