[PATCH] libstdc++: Make internal bit manipulation functions available in C++11.
Jonathan Wakely
jwakely@redhat.com
Wed Aug 19 11:47:47 GMT 2026
On Wed, 05 Aug 2026 at 11:56 +0200, Tomasz Kamiński wrote:
>For __countl_zero, __countr_zero, __popcount we split defintions
>using generic builtin (constexpr in C++11), and typed-builtin (constexpr
>since 20). The __countl_one, __countr_one and __has_single bit, that
>are implemented with single return, as also left constexpr since C++11.
>
>Specializations of __countl_zero, __countr_zero, __popcount and __bit_width
>are provided for __rand_unit128. Using template specializations instead
>of separate overloads, allow them to be selected by __countl_one, and
>other functions that are implemented in terms of above. Despite being
>implemented in terms of __countl_zero, __bit_width is specialized to
>avoid dependency on __gnu_cxx::__int_traits.
>
>The implementation of __bit_floor uses (std::__bit_width(__x) - 1) instead
>of (_Nd - std::__countl_zero((_Tp)(__x >> 1)). This provide supports by
>__rand_uint128 by using new overload. For that type __bit_width(__x) -1,
>is more optimal that __bit_width(__x >> 1).
>
>libstdc++-v3/ChangeLog:
>
> * include/bits/random.h (std::__rotr, std::__rotl, std::__bit_ceil):
> [__cplusplus >= 201103L]: Define as _GLIBCXX14_CONSTEXPR.
> (std::__countl_zero, std::__countr_zero, std::__popcount)
> [__cplusplus >= 201103L]: Split implementation using generic
> builtin, define other as _GLIBCXX14_CONSTEXPR.
> (std::__bit_width, std::__bit_floor) [__cplusplus >= 201103L]:
> Modify to use single return statement.
> * include/bits/random.tcc (std::__countl_zero, std::__countr_zero)
> (std::__popcount, std::__bit_width): Define explicit specializations
> for __detail::__rand_uint128.
> * include/std/bit (std::__generate_canonical_pow2):
> (std::__generate_canonical_any): Replace builtins call with
> <bit> function calls.
>---
>The followup enabling <bit> header in C++11, I have mentioned.
>It makes the function constexpr when possible.
>
>Testing on x86_64 and powerpc64le. *random* tested in all standard
>modes, -m32, debug and assertions.
OK thanks
> libstdc++-v3/include/bits/random.h | 43 +++++++++++++--
> libstdc++-v3/include/bits/random.tcc | 17 ++----
> libstdc++-v3/include/std/bit | 79 ++++++++++++++++------------
> 3 files changed, 88 insertions(+), 51 deletions(-)
>
>diff --git a/libstdc++-v3/include/bits/random.h b/libstdc++-v3/include/bits/random.h
>index b01b92862cc..cfec087f0cd 100644
>--- a/libstdc++-v3/include/bits/random.h
>+++ b/libstdc++-v3/include/bits/random.h
>@@ -31,6 +31,7 @@
> #ifndef _RANDOM_H
> #define _RANDOM_H 1
>
>+#include <bit> // std::__bit_width
> #include <vector>
> #include <bits/ios_base.h>
> #include <bits/uniform_int_dist.h>
>@@ -68,13 +69,13 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> #endif
>
> /// @cond undocumented
>- // Implementation-space details.
>- namespace __detail
>- {
> #pragma GCC diagnostic push
> #pragma GCC diagnostic ignored "-Wc++17-extensions"
>
> #ifndef __SIZEOF_INT128__
>+ // Implementation-space details.
>+ namespace __detail
>+ {
> // Emulate 128-bit integer type, for the arithmetic ops used in <random>.
> // The __detail::__mod function needs: (type(a) * x + c) % m.
> // std::philox_engine needs multiplication and bitwise ops.
>@@ -522,8 +523,42 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> uint64_t _M_hi = 0;
> uint64_t _M_lo = 0;
> };
>-#endif // ! __SIZEOF_INT128__
>+ } // namespace __detail
>+
>+ template<>
>+ constexpr int
>+ __countl_zero(__detail::__rand_uint128 __val) noexcept
>+ {
>+ return __val._M_hi ? std::__countl_zero(__val._M_hi)
>+ : std::__countl_zero(__val._M_lo) + 64;
>+ }
>
>+ template<>
>+ constexpr int
>+ __countr_zero(__detail::__rand_uint128 __val) noexcept
>+ {
>+ return __val._M_lo ? std::__countr_zero(__val._M_lo)
>+ : std::__countr_zero(__val._M_hi) + 64;
>+ }
>+
>+ template<>
>+ constexpr int
>+ __popcount(__detail::__rand_uint128 __val) noexcept
>+ {
>+ return std::__popcount(__val._M_hi) + std::__popcount(__val._M_lo);
>+ }
>+
>+ template<>
>+ constexpr int
>+ __bit_width(__detail::__rand_uint128 __val) noexcept
>+ {
>+ return __val._M_hi ? std::__bit_width(__val._M_hi) + 64
>+ : std::__bit_width(__val._M_lo);
>+ }
>+
>+#endif // ! __SIZEOF_INT128__
>+ namespace __detail
>+ {
> template<typename _UIntType, size_t __w,
> bool = __w < static_cast<size_t>
> (std::numeric_limits<_UIntType>::digits)>
>diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc
>index b2afe411a7c..370109bd04f 100644
>--- a/libstdc++-v3/include/bits/random.tcc
>+++ b/libstdc++-v3/include/bits/random.tcc
>@@ -3706,10 +3706,10 @@ namespace __detail
> // Commented-out assignments below are of values specified in
> // the Standard, but not used here for reasons noted.
> // r = 2; // Redundant, we only support radix 2.
>- using _Rng = decltype(_Urbg::max());
>- const _Rng __rng_range_less_1 = _Urbg::max() - _Urbg::min();
>+ using _URng = typename make_unsigned<decltype(_Urbg::max())>::type;
>+ const _URng __rng_range_less_1(_Urbg::max() - _Urbg::min());
> // R = _UInt(__rng_range_less_1) + 1; // May wrap to 0.
>- const auto __log2_R = __builtin_popcountg(__rng_range_less_1);
>+ const auto __log2_R = std::__popcount(__rng_range_less_1);
> const auto __log2_uint_max = sizeof(_UInt) * __CHAR_BIT__;
> // rd = _UInt(1) << __d; // Could overflow, UB.
> const unsigned __k = (__d + __log2_R - 1) / __log2_R;
>@@ -3804,8 +3804,7 @@ namespace __detail
> // Cannot overflow, as _Urbg::max() - _Urbg::min() is not power of
> // two minus one
> constexpr _UIntR __R = _UIntR(_Urbg::max() - _Urbg::min()) + 1;
>- constexpr unsigned __log2R
>- = sizeof(_UIntR) * __CHAR_BIT__ - __builtin_clzg(__R) - 1;
>+ constexpr unsigned __log2R = std::__bit_width(__R) - 1;
> // We overstimate number of required bits, by computing
> // m such that m * log2(R) >= d, so:
> // R^m >= (2 ^ log2(R)) ^ m == 2 ^ (log2(R) * m) >= 2^d
>@@ -3872,13 +3871,7 @@ namespace __detail
>
> // __abits is maximum bit width of the value, that can
> // be multiplied by R^l without overflowing 128 bit integer
>- _GLIBCXX_GEN_CANON_CONST unsigned __bwRl
>-#ifndef __SIZEOF_INT128__
>- = __Rl._M_hi ? 128 - __builtin_clzg(__Rl._M_hi)
>- : 64 - __builtin_clzg(__Rl._M_lo);
>-#else
>- = 128 - __builtin_clzg(__Rl);
>-#endif
>+ _GLIBCXX_GEN_CANON_CONST unsigned __bwRl = std::__bit_width(__Rl);
>
> // For __R close to power of two, the actual __k may be smaller than __m,
> // and will use less than 128bits, default to two 32 bits chunks.
>diff --git a/libstdc++-v3/include/std/bit b/libstdc++-v3/include/std/bit
>index 6ea0f6eef83..b735044ca18 100644
>--- a/libstdc++-v3/include/std/bit
>+++ b/libstdc++-v3/include/std/bit
>@@ -33,7 +33,7 @@
> #pragma GCC system_header
> #endif
>
>-#if __cplusplus >= 201402L
>+#if __cplusplus >= 201103L
>
> #include <concepts> // for std::integral
> #include <type_traits>
>@@ -157,7 +157,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
>
> template<typename _Tp>
>- constexpr _Tp
>+ _GLIBCXX14_CONSTEXPR _Tp
> __rotl(_Tp __x, int __s) noexcept
> {
> constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
>@@ -179,7 +179,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> }
>
> template<typename _Tp>
>- constexpr _Tp
>+ _GLIBCXX14_CONSTEXPR _Tp
> __rotr(_Tp __x, int __s) noexcept
> {
> constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
>@@ -200,16 +200,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd)); // rotl(x, -r)
> }
>
>+#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_clzg)
> template<typename _Tp>
> constexpr int
> __countl_zero(_Tp __x) noexcept
>+ {
>+ return __builtin_clzg(__x, __gnu_cxx::__int_traits<_Tp>::__digits);
>+ }
>+#else
>+ template<typename _Tp>
>+ _GLIBCXX14_CONSTEXPR int
>+ __countl_zero(_Tp __x) noexcept
> {
> using __gnu_cxx::__int_traits;
> constexpr auto _Nd = __int_traits<_Tp>::__digits;
>-
>-#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_clzg)
>- return __builtin_clzg(__x, _Nd);
>-#else
> if (__x == 0)
> return _Nd;
>
>@@ -247,8 +251,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> unsigned long long __low = __x & __max_ull;
> return (_Nd - _Nd_ull) + __builtin_clzll(__low);
> }
>-#endif
> }
>+#endif
>
> template<typename _Tp>
> constexpr int
>@@ -257,16 +261,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> return std::__countl_zero<_Tp>((_Tp)~__x);
> }
>
>- template<typename _Tp>
>+#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_ctzg)
>+ template<typename _Tp>
> constexpr int
> __countr_zero(_Tp __x) noexcept
>+ {
>+ return __builtin_ctzg(__x, __gnu_cxx::__int_traits<_Tp>::__digits);
>+ }
>+#else
>+ template<typename _Tp>
>+ _GLIBCXX14_CONSTEXPR int
>+ __countr_zero(_Tp __x) noexcept
> {
> using __gnu_cxx::__int_traits;
> constexpr auto _Nd = __int_traits<_Tp>::__digits;
>-
>-#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_ctzg)
>- return __builtin_ctzg(__x, _Nd);
>-#else
> if (__x == 0)
> return _Nd;
>
>@@ -292,8 +300,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> unsigned long long __high = __x >> _Nd_ull;
> return __builtin_ctzll(__high) + _Nd_ull;
> }
>-#endif
> }
>+#endif
>
> template<typename _Tp>
> constexpr int
>@@ -302,13 +310,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> return std::__countr_zero((_Tp)~__x);
> }
>
>+#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_popcountg)
> template<typename _Tp>
> constexpr int
> __popcount(_Tp __x) noexcept
> {
>-#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_popcountg)
> return __builtin_popcountg(__x);
>+ }
> #else
>+ template<typename _Tp>
>+ _GLIBCXX14_CONSTEXPR int
>+ __popcount(_Tp __x) noexcept
>+ {
> using __gnu_cxx::__int_traits;
> constexpr auto _Nd = __int_traits<_Tp>::__digits;
>
>@@ -332,16 +345,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> unsigned long long __high = __x >> _Nd_ull;
> return __builtin_popcountll(__low) + __builtin_popcountll(__high);
> }
>-#endif
> }
>+#endif
>
> template<typename _Tp>
> constexpr bool
> __has_single_bit(_Tp __x) noexcept
> { return std::__popcount(__x) == 1; }
>
>+ template<typename _Tp>
>+ constexpr int
>+ __bit_width(_Tp __x) noexcept
>+ {
>+ return __gnu_cxx::__int_traits<_Tp>::__digits - std::__countl_zero(__x);
>+ }
>+
> template<typename _Tp>
> constexpr _Tp
>+ __bit_floor(_Tp __x) noexcept
>+ {
>+ return (__x == 0) ? (_Tp)0 : ((_Tp)1u << (std::__bit_width(__x) - 1));
>+ }
>+
>+ template<typename _Tp>
>+ _GLIBCXX14_CONSTEXPR _Tp
> __bit_ceil(_Tp __x) noexcept
> {
> using __gnu_cxx::__int_traits;
>@@ -372,24 +399,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> return (_Tp)1u << __shift_exponent;
> }
>
>- template<typename _Tp>
>- constexpr _Tp
>- __bit_floor(_Tp __x) noexcept
>- {
>- constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
>- if (__x == 0)
>- return 0;
>- return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
>- }
>-
>- template<typename _Tp>
>- constexpr int
>- __bit_width(_Tp __x) noexcept
>- {
>- constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
>- return _Nd - std::__countl_zero(__x);
>- }
>-
> #pragma GCC diagnostic pop
> /// @endcond
>
>@@ -499,5 +508,5 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> _GLIBCXX_END_NAMESPACE_VERSION
> } // namespace std
>
>-#endif // C++14
>+#endif // C++11
> #endif // _GLIBCXX_BIT
>--
>2.55.0
>
>
More information about the Libstdc++
mailing list