ISO/IEC JTC1 SC22 WG21 P0553R4
Jens Maurer <Jens.Maurer@gmx.net>
Target audience: LWG
2019-03-01

P0553R4: Bit operations

Introduction

This paper proposes to add simple free functions for basic bit operations on all unsigned integer types.

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

The papers P0237Rx propose to introduce bit_value, bit_reference, and bit_iterator, higher-level concepts for manipulating individual bits and sequences of bits. In order to implement efficient standard algorithms on bit_iterator, it is expected that implementations use the facilities presented in this paper. By directly exposing the low-level facilities to programmers, they can use them for their own purposes, independent of higher-level abstractions in the standard library.

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

Changes

P0553R0 was favorably reviewed by SG6 (including the function names) and forwarded to LEWG. There are only editorial changes in the P0553R1 revision of the paper.

P0553R1 was favorably reviewed by LEWG with removing the nested inline namespace and using the header <bit>, and forwarded to LWG at the Albuquerque, Fall 2017 meeting.

P0553R2 contains small edits in preparation for LWG review.

P0553R3 reflects LWG review (introduce "Constraints" items, harmonize phrasing "0/1 bits in the value of x", add "nodiscard" for rotl/rotr). It was sent back to LEWG to clarify the open issues (see below).

P0553R4 reflects LEWG decisions in Kona:

Also added a feature-test macro and moved the edits to clause 25.5 [bit], here the <bit> header has meanwhile materialized.

This version was reviewed by LWG during its 2019-03-01 teleconference and tentatively approved for plenary vote in Cologne.

Open issues for LEWG

(none)

Design considerations

These operations can be made available either in the <bit> header proposed by P0237R4, or in a separate header. LEWG decided to use <bit>.

The bit rotation operations are not limited to rotation counts less than the bit-width of the integer; it seems most (all?) CPU instruction sets support longer rotations by simply discarding upper bits. Different from bit shifts, this behavior is reasonable because rotating a 32-bit quantity by 33 bits is indistinguishable from rotating it by 1 bit.

The counting operations return "int" quantities, consistent with the rule "use an int unless you need something else". This choice does not reflect, in the type, the fact that counts are always non-negative.

This proposal uses readable English names for the operations, except that "left" (towards/affecting the most significant bits) and "right" (towards/affecting the least significant bits) is abbreviate "l" and "r", respectively. The use of "left" and "right" in the operation names is consistent with the "left" and "right" built-in shift operators.

An earlier draft of this paper had names such as "countl1", but lower-case "ell" and the digit "one" are nearly indistinguishable in some fonts, so now a name like "countl_one" is proposed. This is slightly baroque, so alternatively "countl(T, bool)" could be used, with the understanding that the second parameter is often a compile-time constant, allowing for optimization opportunities.

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 marked constexpr, assuming that either compiler intrinsics that work in constant evaluation are available to the implementation, or the optimizer is good enough to use the appropriate hardware instructions for operations described with potentially verbose expressions with built-in operators.

A tangentially related std::bit_cast is proposed in P0476R1: "Bit-casting object representations" by JF Bastien.

Hardware

This is an incomplete table showing the extent of hardware support for the proposed operations.

operation Intel/AMD ARM PowerPC
rotl ROL - rldicl
rotr ROR ROR, EXTR-
popcount POPCNT - popcntb
countl_zero BSR, LZCNTCLZ cntlzd
countl_one - CLS -
countr_zero BSF, TZCNT- -
countr_one - - -

Wording

Add a new feature-test macro in [support.limits.general] table 36:
Macro name: __cpp_lib_bitops
Value: 201907L
Header: <bit>
Add to the header <bit> synopsis in subclause 25.5.2 [bit.syn]:
namespace std {
  // 25.5.5, rotating   
  template<class T>
    [[nodiscard]] constexpr T rotl(T x, int s) noexcept;
  template<class T>
    [[nodiscard]] constexpr T rotr(T x, int s) noexcept;

  // 25.5.6, counting
  template<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;
}
Add a new subclause at the end of [bit]:

25.5.5 Rotating [bitops.rot]

In the following descriptions, let N denote std::numeric_limits<T>::digits.
  template<class T>
    [[nodiscard]] constexpr T rotl(T x, int s) noexcept;
Constraints: T is an unsigned integer type (3.9.1 [basic.fundamental]).

Let r be s % N.

Returns: If r is 0, x; if r is positive, (x << r) | (x >> (N - r)); if r is negative, rotr(x, -r).

  template<class T>
    [[nodiscard]] constexpr T rotr(T x, int s) noexcept;
Constraints: T is an unsigned integer type (3.9.1 [basic.fundamental]).

Let r be s % N.

Returns: If r is 0, x; if r is positive, (x >> r) | (x << (N - r)); if r is negative, rotl(x, -r).

Add a new subclause at the end of [bit]:

25.5.6 Counting [bitops.count]

In the following descriptions, let N denote std::numeric_limits<T>::digits.
  template<class T>
    constexpr int countl_zero(T x) noexcept;
Constraints: T is an unsigned integer type (3.9.1 [basic.fundamental]).

Returns: The number of consecutive 0 bits in the value of x, starting from the most significant bit. [ Note: Returns N if x == 0. ]

  template<class T>
    constexpr int countl_one(T x) noexcept;
Constraints: T is an unsigned integer type (3.9.1 [basic.fundamental]).

Returns: The number of consecutive 1 bits in the value of x, starting from the most significant bit. [ Note: Returns N if x == std::numeric_limits<T>::max(). ]

  template<class T>
    constexpr int countr_zero(T x) noexcept;
Constraints: T is an unsigned integer type (3.9.1 [basic.fundamental]).

Returns: The number of consecutive 0 bits in the value of x, starting from the least significant bit. [ Note: Returns N if x == 0. ]

  template<class T>
    constexpr int countr_one(T x) noexcept;
Constraints: T is an unsigned integer type (3.9.1 [basic.fundamental]).

Returns: The number of consecutive 1 bits in the value of x, starting from the least significant bit. [ Note: Returns N if x == std::numeric_limits<T>::max(). ]

  template<class T>
    constexpr int popcount(T x) noexcept;
Constraints: T is an unsigned integer type (3.9.1 [basic.fundamental]).

Returns: The number of 1 bits in the value of x.

References