ISO/IEC JTC1 SC22 WG21 P0556R3
Jens Maurer <Jens.Maurer@gmx.net>
Target audience: LWG
2018-06-06

P0556R3: 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 P0214R3: "Data-Parallel Vector Types & Operations" by Matthias Kretz).

Changes

P0556R0 was favorably reviewed by SG6 and passed to LEWG with the following changes: P0556R1 was favorably reviewed by LEWG with the following changes:

Design considerations

The functions are provided for unsigned operands only, since the domain of the proposed functions is positive.

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 contract, 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.

Wording

Add the header <bit> to the table in 17.5.1.2 [headers].

Append a new subsection to clause 29 [numerics] with the following content:

29.10 Integral powers of 2 [numerics.pow.two]

29.10.1 Header <bit> synopsis [bit.syn]

namespace std {
  template <class T>
    constexpr bool ispow2(T x) noexcept;
  template <class T>
    constexpr T ceil2(T x) noexcept;
  template <class T>
    constexpr T floor2(T x) noexcept;
  template <class T>
    constexpr T log2p1(T x) noexcept;
}

29.10.1 Operations [numerics.pow.two.ops]

  template <class T>
    constexpr bool ispow2(T x) noexcept;
Returns: true if x is an integral power of two; false otherwise.

Remarks: This function shall not participate in overload resolution unless T is an unsigned integer type (3.9.1 [basic.fundamental]). 

  template <class T>
    constexpr T ceil2(T x) noexcept;
Returns: The minimal value y such that ispow2(y) is true and y >= x; if y is not representable as a value of type T, the result is an unspecified value.

Remarks: This function shall not participate in overload resolution unless T is an unsigned integer type (3.9.1 [basic.fundamental]). 

  template <class T>
    constexpr T floor2(T x) noexcept;
Returns: If x == 0, 0; otherwise the maximal value y such that ispow2(y) is true and y <= x.

Remarks: This function shall not participate in overload resolution unless T is an unsigned integer type (3.9.1 [basic.fundamental]). 

  template <class T>
    constexpr T log2p1(T x) noexcept;
Returns: If x == 0, 0; otherwise one plus the base-2 logarithm of x, with any fractional part discarded.

Remarks: This function shall not participate in overload resolution unless T is an unsigned integer type (3.9.1 [basic.fundamental]).

References