Re: [PATCH] libstdc++: Make internal bit manipulation functions available in C++11.

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