// -*- C++ -*-
//===----------------------------------------------------------------------===//
//
// Part of libcu++, the C++ Standard Library for your entire system,
// under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// SPDX-FileCopyrightText: Copyright (c) 2024 NVIDIA CORPORATION & AFFILIATES.
//
//===----------------------------------------------------------------------===//

#ifndef _CUDA_STD_BITSET
#define _CUDA_STD_BITSET

#include <cuda/std/detail/__config>

#if defined(_CCCL_IMPLICIT_SYSTEM_HEADER_GCC)
#  pragma GCC system_header
#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_CLANG)
#  pragma clang system_header
#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_MSVC)
#  pragma system_header
#endif // no system header

#include <cuda/std/__algorithm/count.h>
#include <cuda/std/__algorithm/fill.h>
#include <cuda/std/__algorithm/find.h>
#include <cuda/std/__bit/reference.h>
#include <cuda/std/__functional/hash.h>
#include <cuda/std/__functional/unary_function.h>
#include <cuda/std/__type_traits/is_char_like_type.h>
#include <cuda/std/climits>
#include <cuda/std/cstddef>
#include <cuda/std/detail/libcxx/include/__assert> // all public C++ headers provide the assertion handler
#include <cuda/std/detail/libcxx/include/__string>
#include <cuda/std/detail/libcxx/include/stdexcept>
#if defined(_LIBCUDACXX_HAS_STRING_VIEW)
#  include <cuda/std/string_view>
#endif // _LIBCUDACXX_HAS_STRING_VIEW
#include <cuda/std/version>

// standard-mandated includes

// [bitset.syn]
#include <cuda/std/detail/libcxx/include/iosfwd>
#if defined(_LIBCUDACXX_HAS_STRING)
#  include <cuda/std/string>
#endif // _LIBCUDACXX_HAS_STRING

_CCCL_PUSH_MACROS

_LIBCUDACXX_BEGIN_NAMESPACE_STD

template <class _Int>
struct __avoid_promotions
{
  using __base = __conditional_t<(sizeof(_Int) >= sizeof(int)),
                                 _Int,
                                 __conditional_t<is_unsigned<_Int>::value, unsigned int, signed int>>;

  _CCCL_HIDE_FROM_ABI constexpr __avoid_promotions() = default;

  template <class _Tp, typename = __enable_if_t<_CCCL_TRAIT(is_integral, _Tp)>>
  _CCCL_HOST_DEVICE constexpr __avoid_promotions(_Tp __i)
      : __data(static_cast<_Int>(__i))
  {}

  _CCCL_HOST_DEVICE constexpr explicit operator bool() const
  {
    return static_cast<bool>(__data);
  }

  // helper for fill_n
  _CCCL_HOST_DEVICE constexpr friend _Int __convert_to_integral(__avoid_promotions __self)
  {
    return __self.__data;
  }

#define _DEFINE_UNARY(__op)                                                                         \
  _CCCL_HOST_DEVICE constexpr friend __avoid_promotions operator __op(__avoid_promotions __operand) \
  {                                                                                                 \
    return __avoid_promotions(static_cast<_Int>(__op static_cast<__base>(__operand.__data)));       \
  }

  _DEFINE_UNARY(~)
  _CCCL_DIAG_PUSH
  _CCCL_DIAG_SUPPRESS_MSVC(4146) // unary minus applied to an unsigned type
  _DEFINE_UNARY(-)
  _CCCL_DIAG_POP
#undef _DEFINE_UNARY

#define _DEFINE_SHIFT(__op)                                                                                            \
  template <class _Tp>                                                                                                 \
  _CCCL_HOST_DEVICE constexpr friend __avoid_promotions operator __op(__avoid_promotions __operand, _Tp __n)           \
  {                                                                                                                    \
    return __avoid_promotions(static_cast<_Int>(static_cast<__base>(__operand.__data) __op static_cast<__base>(__n))); \
  }                                                                                                                    \
  template <class _Tp>                                                                                                 \
  _CCCL_HOST_DEVICE constexpr friend __avoid_promotions operator __op(                                                 \
    __avoid_promotions __operand, __avoid_promotions<_Tp> __n)                                                         \
  {                                                                                                                    \
    return __avoid_promotions(                                                                                         \
      static_cast<_Int>(static_cast<__base>(__operand.__data) __op static_cast<__base>(__n.__data)));                  \
  }

  _DEFINE_SHIFT(<<)
  _DEFINE_SHIFT(>>)
#undef _DEFINE_SHIFT

#define _DEFINE_SHIFT_ASSIGNMENT(__op)                                                       \
  template <class _Tp>                                                                       \
  _CCCL_HOST_DEVICE _CCCL_CONSTEXPR_CXX14 __avoid_promotions& operator __op##=(_Tp __n)      \
  {                                                                                          \
    if (__n >= sizeof(_Int) * CHAR_BIT)                                                      \
    {                                                                                        \
      __data = 0;                                                                            \
    }                                                                                        \
    else                                                                                     \
    {                                                                                        \
      __data = static_cast<_Int>(static_cast<__base>(__data) __op static_cast<__base>(__n)); \
    }                                                                                        \
    return *this;                                                                            \
  }

  _DEFINE_SHIFT_ASSIGNMENT(<<)
  _DEFINE_SHIFT_ASSIGNMENT(>>)
#undef _DEFINE_SHIFT_ASSIGNMENT

#define _DEFINE_BINARY(__op)                                                                        \
  _CCCL_HOST_DEVICE constexpr friend __avoid_promotions operator __op(                              \
    __avoid_promotions __lhs, __avoid_promotions __rhs)                                             \
  {                                                                                                 \
    return __avoid_promotions(                                                                      \
      static_cast<_Int>(static_cast<__base>(__lhs.__data) __op static_cast<__base>(__rhs.__data))); \
  }

  _DEFINE_BINARY(+)
  _DEFINE_BINARY(-)
  _DEFINE_BINARY(*)
  _DEFINE_BINARY(/)
  _DEFINE_BINARY(%)
  _DEFINE_BINARY(&)
  _DEFINE_BINARY(|)
  _DEFINE_BINARY(^)
#undef _DEFINE_BINARY

#define _DEFINE_ASSIGNMENT(__op)                                                                         \
  _CCCL_HOST_DEVICE _CCCL_CONSTEXPR_CXX14 __avoid_promotions& operator __op##=(__avoid_promotions __rhs) \
  {                                                                                                      \
    __data = static_cast<_Int>(static_cast<__base>(__data) __op static_cast<__base>(__rhs.__data));      \
    return *this;                                                                                        \
  }

  _DEFINE_ASSIGNMENT(+)
  _DEFINE_ASSIGNMENT(-)
  _DEFINE_ASSIGNMENT(*)
  _DEFINE_ASSIGNMENT(/)
  _DEFINE_ASSIGNMENT(%)
  _DEFINE_ASSIGNMENT(&)
  _DEFINE_ASSIGNMENT(|)
  _DEFINE_ASSIGNMENT(^)
#undef _DEFINE_ASSIGNMENT

#define _DEFINE_COMPARISON(__op)                                                                            \
  _CCCL_HOST_DEVICE constexpr friend bool operator __op(__avoid_promotions __lhs, __avoid_promotions __rhs) \
  {                                                                                                         \
    return static_cast<_Int>(static_cast<__base>(__lhs.__data) __op static_cast<__base>(__rhs.__data));     \
  }

  _DEFINE_COMPARISON(<)
  _DEFINE_COMPARISON(>)
  _DEFINE_COMPARISON(==)
#if _CCCL_STD_VER <= 2017
  _DEFINE_COMPARISON(!=)
#endif
#undef _DEFINE_COMPARISON

  _Int __data;
};

static_assert(sizeof(__avoid_promotions<uint_least8_t>) == sizeof(uint_least8_t), "");
static_assert(sizeof(__avoid_promotions<uint_least16_t>) == sizeof(uint_least16_t), "");
static_assert(sizeof(__avoid_promotions<uint_least32_t>) == sizeof(uint_least32_t), "");

template <size_t _N_words, size_t _Size>
class __bitset
{
public:
  typedef ptrdiff_t difference_type;
  typedef size_t size_type;
  typedef __avoid_promotions<uint32_t> __storage_type;

protected:
  typedef __bitset __self;
  typedef __storage_type* __storage_pointer;
  typedef const __storage_type* __const_storage_pointer;
  static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);

  friend class __bit_reference<__bitset>;
  friend class __bit_const_reference<__bitset>;
  friend class __bit_iterator<__bitset, false>;
  friend class __bit_iterator<__bitset, true>;
  friend struct __bit_array<__bitset>;

  __storage_type __first_[_N_words];

  typedef __bit_reference<__bitset> reference;
  typedef __bit_const_reference<__bitset> const_reference;
  typedef __bit_iterator<__bitset, false> iterator;
  typedef __bit_iterator<__bitset, true> const_iterator;

  _LIBCUDACXX_HIDE_FROM_ABI static constexpr __storage_type __clip_top_word_to_size(unsigned long long __v)
  {
    return _Size >= 2 * __bits_per_word
           ? static_cast<__storage_type>(__v >> __bits_per_word)
           : static_cast<__storage_type>(
               (__v >> __bits_per_word) & ((__storage_type(1) << (_Size - __bits_per_word)) - 1));
  }

  _LIBCUDACXX_HIDE_FROM_ABI constexpr __bitset() noexcept
      : __first_{0}
  {}

  _LIBCUDACXX_HIDE_FROM_ABI explicit constexpr __bitset(unsigned long long __v) noexcept
      : __first_{static_cast<__storage_type>(__v), __clip_top_word_to_size(__v)}
  {}

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 reference __make_ref(size_t __pos) noexcept
  {
    return reference(__first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);
  }
  _LIBCUDACXX_HIDE_FROM_ABI constexpr const_reference __make_ref(size_t __pos) const noexcept
  {
    return const_reference(__first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);
  }
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 iterator __make_iter(size_t __pos) noexcept
  {
    return iterator(__first_ + __pos / __bits_per_word, __pos % __bits_per_word);
  }
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 const_iterator __make_iter(size_t __pos) const noexcept
  {
    return const_iterator(__first_ + __pos / __bits_per_word, __pos % __bits_per_word);
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void operator&=(const __bitset& __v) noexcept
  {
    for (size_type __i = 0; __i < _N_words; ++__i)
    {
      __first_[__i] &= __v.__first_[__i];
    }
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void operator|=(const __bitset& __v) noexcept
  {
    for (size_type __i = 0; __i < _N_words; ++__i)
    {
      __first_[__i] |= __v.__first_[__i];
    }
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void operator^=(const __bitset& __v) noexcept
  {
    for (size_type __i = 0; __i < _N_words; ++__i)
    {
      __first_[__i] ^= __v.__first_[__i];
    }
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 __bitset& operator<<=(size_t __pos) noexcept
  {
    __pos = _CUDA_VSTD::min(__pos, _Size);
    _CUDA_VSTD::copy_backward(__make_iter(0), __make_iter(_Size - __pos), __make_iter(_Size));
    _CUDA_VSTD::fill_n(__make_iter(0), __pos, false);
    return *this;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 __bitset& operator>>=(size_t __pos) noexcept
  {
    __pos = _CUDA_VSTD::min(__pos, _Size);
    _CUDA_VSTD::copy(__make_iter(__pos), __make_iter(_Size), __make_iter(0));
    _CUDA_VSTD::fill_n(__make_iter(_Size - __pos), __pos, false);
    return *this;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void flip() noexcept
  {
    // do middle whole words
    size_type __n         = _Size;
    __storage_pointer __p = __first_;
    for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
    {
      *__p = ~*__p;
    }
    // do last partial word
    if (__n > 0)
    {
      __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
      __storage_type __b = *__p & __m;
      *__p &= ~__m;
      *__p |= ~__b & __m;
    }
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 unsigned long to_ulong() const
  {
    return to_ulong(integral_constant<bool, _Size <= sizeof(unsigned long) * CHAR_BIT>());
  }
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 unsigned long long to_ullong() const
  {
    return to_ullong(integral_constant<bool, _Size <= sizeof(unsigned long long) * CHAR_BIT>());
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bool all() const noexcept
  {
    // do middle whole words
    size_type __n               = _Size;
    __const_storage_pointer __p = __first_;
    for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
    {
      if (~*__p)
      {
        return false;
      }
    }
    // do last partial word
    if (__n > 0)
    {
      __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
      if (~*__p & __m)
      {
        return false;
      }
    }
    return true;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bool any() const noexcept
  {
    // do middle whole words
    size_type __n               = _Size;
    __const_storage_pointer __p = __first_;
    for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
    {
      if (*__p)
      {
        return true;
      }
    }
    // do last partial word
    if (__n > 0)
    {
      __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
      if (*__p & __m)
      {
        return true;
      }
    }
    return false;
  }

  _LIBCUDACXX_HIDE_FROM_ABI size_t __hash_code() const noexcept
  {
    size_t __h = 0;
    for (size_type __i = 0; __i < _N_words; ++__i)
    {
      __h ^= __first_[__i];
    }
    return __h;
  }

private:
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 unsigned long to_ulong(false_type) const
  {
    const_iterator __e = __make_iter(_Size);
    const_iterator __i = _CUDA_VSTD::find(__make_iter(sizeof(unsigned long) * CHAR_BIT), __e, true);
    if (__i != __e)
    {
      _CUDA_VSTD::__throw_overflow_error("bitset to_ulong overflow error");
    }

    return to_ulong(true_type());
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 unsigned long to_ulong(true_type) const
  {
    return to_ulong(true_type(), integral_constant<bool, sizeof(__storage_type) <= sizeof(unsigned long)>());
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 unsigned long to_ulong(true_type, false_type) const
  {
    return __first_[0].__data;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 unsigned long to_ulong(true_type, true_type) const
  {
    unsigned long __r = __first_[0].__data;
    for (size_t __i = 1; __i < sizeof(unsigned long) / sizeof(__storage_type); ++__i)
    {
      __r |= static_cast<unsigned long>(__first_[__i].__data) << (__i * sizeof(__storage_type) * CHAR_BIT);
    }
    return __r;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 unsigned long long to_ullong(false_type) const
  {
    const_iterator __e = __make_iter(_Size);
    const_iterator __i = _CUDA_VSTD::find(__make_iter(sizeof(unsigned long long) * CHAR_BIT), __e, true);
    if (__i != __e)
    {
      _CUDA_VSTD::__throw_overflow_error("bitset to_ullong overflow error");
    }

    return to_ullong(true_type());
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 unsigned long long to_ullong(true_type) const
  {
    return to_ullong(true_type(), integral_constant<bool, sizeof(__storage_type) <= sizeof(unsigned long long)>());
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 unsigned long long to_ullong(true_type, false_type) const
  {
    return __first_[0].__data;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 unsigned long long to_ullong(true_type, true_type) const
  {
    unsigned long long __r = __first_[0].__data;
    for (size_t __i = 1; __i < sizeof(unsigned long long) / sizeof(__storage_type); ++__i)
    {
      __r |= static_cast<unsigned long long>(__first_[__i].__data) << (__i * sizeof(__storage_type) * CHAR_BIT);
    }
    return __r;
  }
};

template <size_t _Size>
class __bitset<1, _Size>
{
public:
  typedef ptrdiff_t difference_type;
  typedef size_t size_type;
  typedef __avoid_promotions<__conditional_t<_Size <= 8, uint8_t, __conditional_t<_Size <= 16, uint16_t, uint32_t>>>
    __storage_type;

protected:
  typedef __bitset __self;
  typedef __storage_type* __storage_pointer;
  typedef const __storage_type* __const_storage_pointer;
  static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);

  friend class __bit_reference<__bitset>;
  friend class __bit_const_reference<__bitset>;
  friend class __bit_iterator<__bitset, false>;
  friend class __bit_iterator<__bitset, true>;
  friend struct __bit_array<__bitset>;

  __storage_type __first_;

  typedef __bit_reference<__bitset> reference;
  typedef __bit_const_reference<__bitset> const_reference;
  typedef __bit_iterator<__bitset, false> iterator;
  typedef __bit_iterator<__bitset, true> const_iterator;

  _LIBCUDACXX_HIDE_FROM_ABI constexpr __bitset() noexcept
      : __first_(0)
  {}

  _CCCL_DIAG_PUSH
  _CCCL_DIAG_SUPPRESS_MSVC(4293) // shift count negative or too big
                                 // MSVC is slightly overeager with diagnosing that here
  _LIBCUDACXX_HIDE_FROM_ABI explicit constexpr __bitset(unsigned long long __v) noexcept
      : __first_(_Size == __bits_per_word
                   ? static_cast<__storage_type>(__v)
                   : static_cast<__storage_type>(__v) & ((__storage_type(1) << _Size) - __storage_type(1)))
  {}
  _CCCL_DIAG_POP

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 reference __make_ref(size_t __pos) noexcept
  {
    return reference(&__first_, __storage_type(1) << __pos);
  }
  _LIBCUDACXX_HIDE_FROM_ABI constexpr const_reference __make_ref(size_t __pos) const noexcept
  {
    return const_reference(&__first_, __storage_type(1) << __pos);
  }
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 iterator __make_iter(size_t __pos) noexcept
  {
    return iterator(&__first_ + __pos / __bits_per_word, __pos % __bits_per_word);
  }
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 const_iterator __make_iter(size_t __pos) const noexcept
  {
    return const_iterator(&__first_ + __pos / __bits_per_word, __pos % __bits_per_word);
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void operator&=(const __bitset& __v) noexcept
  {
    __first_ &= __v.__first_;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void operator|=(const __bitset& __v) noexcept
  {
    __first_ |= __v.__first_;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void operator^=(const __bitset& __v) noexcept
  {
    __first_ ^= __v.__first_;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void operator<<=(size_t __rhs) noexcept
  {
    __first_ <<= __rhs;
    __first_ &= ~__storage_type(0) >> (__bits_per_word - _Size);
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void operator>>=(size_t __rhs) noexcept
  {
    __first_ >>= __rhs;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void flip() noexcept
  {
    __storage_type __m = ~__storage_type(0) >> (__bits_per_word - _Size);
    __first_           = ~__first_;
    __first_ &= __m;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 unsigned long to_ulong() const
  {
#ifdef _CCCL_COMPILER_MSVC
    if (static_cast<unsigned long>(__first_.__data) != __first_.__data)
    {
      _CUDA_VSTD::__throw_overflow_error("bitset to_ulong overflow error");
    }
    return static_cast<unsigned long>(__first_.__data);
#else // ^^ MSVC ^^ | vv !MSVC vv
    return __first_.__data;
#endif // !MSVC
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 unsigned long long to_ullong() const
  {
    return __first_.__data;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bool all() const noexcept
  {
    __storage_type __m = ~__storage_type(0) >> (__bits_per_word - _Size);
    return !static_cast<bool>(~__first_ & __m);
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bool any() const noexcept
  {
    __storage_type __m = ~__storage_type(0) >> (__bits_per_word - _Size);
    return static_cast<bool>(__first_ & __m);
  }

  _LIBCUDACXX_HIDE_FROM_ABI size_t __hash_code() const noexcept
  {
    return __first_;
  }
};

template <>
class __bitset<0, 0>
{
public:
  typedef ptrdiff_t difference_type;
  typedef size_t size_type;
  typedef __avoid_promotions<uint32_t> __storage_type;

protected:
  typedef __bitset __self;
  typedef __storage_type* __storage_pointer;
  typedef const __storage_type* __const_storage_pointer;
  static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);

  friend class __bit_reference<__bitset>;
  friend class __bit_const_reference<__bitset>;
  friend class __bit_iterator<__bitset, false>;
  friend class __bit_iterator<__bitset, true>;
  friend struct __bit_array<__bitset>;

  typedef __bit_reference<__bitset> reference;
  typedef __bit_const_reference<__bitset> const_reference;
  typedef __bit_iterator<__bitset, false> iterator;
  typedef __bit_iterator<__bitset, true> const_iterator;

  _LIBCUDACXX_HIDE_FROM_ABI constexpr __bitset() noexcept {}
  _LIBCUDACXX_HIDE_FROM_ABI explicit constexpr __bitset(unsigned long long) noexcept {}

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 reference __make_ref(size_t) noexcept
  {
    return reference(nullptr, 1);
  }
  _LIBCUDACXX_HIDE_FROM_ABI constexpr const_reference __make_ref(size_t) const noexcept
  {
    return const_reference(nullptr, 1);
  }
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 iterator __make_iter(size_t) noexcept
  {
    return iterator(nullptr, 0);
  }
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 const_iterator __make_iter(size_t) const noexcept
  {
    return const_iterator(nullptr, 0);
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void operator&=(const __bitset&) noexcept {}
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void operator|=(const __bitset&) noexcept {}
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void operator^=(const __bitset&) noexcept {}
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void operator<<=(size_t) noexcept {}
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void operator>>=(size_t) noexcept {}

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void flip() noexcept {}

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 unsigned long to_ulong() const
  {
    return 0;
  }
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 unsigned long long to_ullong() const
  {
    return 0;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bool all() const noexcept
  {
    return true;
  }
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bool any() const noexcept
  {
    return false;
  }

  _LIBCUDACXX_HIDE_FROM_ABI size_t __hash_code() const noexcept
  {
    return 0;
  }
};

template <size_t _Size>
class _CCCL_TYPE_VISIBILITY_DEFAULT bitset;
template <size_t _Size>
struct hash<bitset<_Size>>;

template <size_t _Size>
_LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void __throw_if_out_of_range(size_t __pos, const char* __msg)
{
  if (__pos >= _Size)
  {
    _CUDA_VSTD::__throw_out_of_range(__msg);
  }
}

template <>
_LIBCUDACXX_HIDE_FROM_ABI void __throw_if_out_of_range<0>(size_t __pos, const char* __msg)
{
  _CUDA_VSTD::__throw_out_of_range(__msg);
}

template <size_t _Size>
class _CCCL_TYPE_VISIBILITY_DEFAULT bitset : private __bitset<_Size == 0 ? 0 : (_Size - 1) / 32 + 1, _Size>
{
public:
  static const unsigned __n_words = _Size == 0 ? 0 : (_Size - 1) / 32 + 1;
  typedef __bitset<__n_words, _Size> base;

public:
  typedef typename base::reference reference;
  typedef typename base::const_reference const_reference;

  // 23.3.5.1 constructors:
  _LIBCUDACXX_HIDE_FROM_ABI constexpr bitset() noexcept {}
  _LIBCUDACXX_HIDE_FROM_ABI constexpr bitset(unsigned long long __v) noexcept
      : base(__v)
  {}
  template <class _CharT, class = __enable_if_t<_IsCharLikeType<_CharT>::value>>
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 explicit bitset(
    const _CharT* __str, size_t __n = static_cast<size_t>(-1), _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'))
  {
    size_t __rlen = _CUDA_VSTD::min(__n, char_traits<_CharT>::length(__str));
#if defined(_LIBCUDACXX_HAS_STRING_VIEW)
    __init_from_string_view(basic_string_view<_CharT>(__str, __rlen), __zero, __one);
#else
    __init_from_cstr(__str, __rlen, __zero, __one);
#endif
  }
#if defined(_LIBCUDACXX_HAS_STRING_VIEW)
  template <class _CharT, class _Traits>
  _LIBCUDACXX_HIDE_FROM_ABI constexpr explicit bitset(
    basic_string_view<_CharT, _Traits> __str,
    typename basic_string_view<_CharT, _Traits>::size_type __pos = 0,
    typename basic_string_view<_CharT, _Traits>::size_type __n   = basic_string_view<_CharT, _Traits>::npos,
    _CharT __zero                                                = _CharT('0'),
    _CharT __one                                                 = _CharT('1'))
  {
    if (__pos > __str.size())
    {
      _CUDA_VSTD::__throw_out_of_range("bitset string pos out of range");
    }

    size_t __rlen = _CUDA_VSTD::min(__n, __str.size() - __pos);
    __init_from_string_view(basic_string_view<_CharT, _Traits>(__str.data() + __pos, __rlen), __zero, __one);
  }
#endif // defined(_LIBCUDACXX_HAS_STRING_VIEW)
#if defined(_LIBCUDACXX_HAS_STRING)
  template <class _CharT, class _Traits, class _Allocator>
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 explicit bitset(
    const basic_string<_CharT, _Traits, _Allocator>& __str,
    typename basic_string<_CharT, _Traits, _Allocator>::size_type __pos = 0,
    typename basic_string<_CharT, _Traits, _Allocator>::size_type __n = basic_string<_CharT, _Traits, _Allocator>::npos,
    _CharT __zero                                                     = _CharT('0'),
    _CharT __one                                                      = _CharT('1'))
  {
    if (__pos > __str.size())
    {
      _CUDA_VSTD::__throw_out_of_range("bitset string pos out of range");
    }

    size_t __rlen = _CUDA_VSTD::min(__n, __str.size() - __pos);
    __init_from_string_view(basic_string_view<_CharT, _Traits>(__str.data() + __pos, __rlen), __zero, __one);
  }
#endif // defined(_LIBCUDACXX_HAS_STRING)

  // 23.3.5.2 bitset operations:
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bitset& operator&=(const bitset& __rhs) noexcept
  {
    base::operator&=(__rhs);
    return *this;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bitset& operator|=(const bitset& __rhs) noexcept
  {
    base::operator|=(__rhs);
    return *this;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bitset& operator^=(const bitset& __rhs) noexcept
  {
    base::operator^=(__rhs);
    return *this;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bitset& operator<<=(size_t __rhs) noexcept
  {
    base::operator<<=(__rhs);
    return *this;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bitset& operator>>=(size_t __rhs) noexcept
  {
    base::operator>>=(__rhs);
    return *this;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bitset& set() noexcept
  {
    _CUDA_VSTD::fill_n(base::__make_iter(0), _Size, true);
    return *this;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bitset& set(size_t __pos, bool __val = true)
  {
    _CUDA_VSTD::__throw_if_out_of_range<_Size>(__pos, "bitset set argument out of range");

    (*this)[__pos] = __val;
    return *this;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bitset& reset() noexcept
  {
    _CUDA_VSTD::fill_n(base::__make_iter(0), _Size, false);
    return *this;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bitset& reset(size_t __pos)
  {
    _CUDA_VSTD::__throw_if_out_of_range<_Size>(__pos, "bitset reset argument out of range");

    (*this)[__pos] = false;
    return *this;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bitset operator~() const noexcept
  {
    bitset __x(*this);
    __x.flip();
    return __x;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bitset& flip() noexcept
  {
    base::flip();
    return *this;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bitset& flip(size_t __pos)
  {
    _CUDA_VSTD::__throw_if_out_of_range<_Size>(__pos, "bitset flip argument out of range");

    reference __r = base::__make_ref(__pos);
    __r           = ~__r;
    return *this;
  }

  // element access:
#ifdef _LIBCUDACXX_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL
  _LIBCUDACXX_HIDE_FROM_ABI constexpr bool operator[](size_t __p) const
  {
    return base::__make_ref(__p);
  }
#else
  _LIBCUDACXX_HIDE_FROM_ABI constexpr const_reference operator[](size_t __p) const
  {
    return base::__make_ref(__p);
  }
#endif
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 reference operator[](size_t __p)
  {
    return base::__make_ref(__p);
  }
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 unsigned long to_ulong() const
  {
    return base::to_ulong();
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 unsigned long long to_ullong() const
  {
    return base::to_ullong();
  }

#if defined(_LIBCUDACXX_HAS_STRING)
  template <class _CharT, class _Traits, class _Allocator>
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 basic_string<_CharT, _Traits, _Allocator>
  to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
  {
    basic_string<_CharT, _Traits, _Allocator> __r(_Size, __zero);
    for (size_t __i = 0; __i != _Size; ++__i)
    {
      if ((*this)[__i])
      {
        __r[_Size - 1 - __i] = __one;
      }
    }
    return __r;
  }

  template <class _CharT, class _Traits>
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 basic_string<_CharT, _Traits, allocator<_CharT>>
  to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
  {
    return to_string<_CharT, _Traits, allocator<_CharT>>(__zero, __one);
  }

  template <class _CharT>
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 basic_string<_CharT, char_traits<_CharT>, allocator<_CharT>>
  to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
  {
    return to_string<_CharT, char_traits<_CharT>, allocator<_CharT>>(__zero, __one);
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 basic_string<char, char_traits<char>, allocator<char>>
  to_string(char __zero = '0', char __one = '1') const
  {
    return to_string<char, char_traits<char>, allocator<char>>(__zero, __one);
  }
#endif // defined(_LIBCUDACXX_HAS_STRING)
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 size_t count() const noexcept
  {
    return static_cast<size_t>(_CUDA_VSTD::count(base::__make_iter(0), base::__make_iter(_Size), true));
  }

  _LIBCUDACXX_HIDE_FROM_ABI constexpr size_t size() const noexcept
  {
    return _Size;
  }
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bool operator==(const bitset& __rhs) const noexcept
  {
    return _CUDA_VSTD::equal(base::__make_iter(0), base::__make_iter(_Size), __rhs.__make_iter(0));
  }

#if _CCCL_STD_VER <= 2017
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bool operator!=(const bitset& __rhs) const noexcept
  {
    return !(*this == __rhs);
  }
#endif // C++ <= 17

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bool test(size_t __pos) const
  {
    _CUDA_VSTD::__throw_if_out_of_range<_Size>(__pos, "bitset test argument out of range");

    return (*this)[__pos];
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bool all() const noexcept
  {
    return base::all();
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bool any() const noexcept
  {
    return base::any();
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bool none() const noexcept
  {
    return !any();
  }
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bitset operator<<(size_t __pos) const noexcept
  {
    bitset __r = *this;
    __r <<= __pos;
    return __r;
  }

  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bitset operator>>(size_t __pos) const noexcept
  {
    bitset __r = *this;
    __r >>= __pos;
    return __r;
  }

private:
#if defined(_LIBCUDACXX_HAS_STRING_VIEW)
  template <class _CharT, class _Traits>
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void
  __init_from_string_view(basic_string_view<_CharT, _Traits> __str, _CharT __zero, _CharT __one)
  {
    for (size_t __i = 0; __i < __str.size(); ++__i)
    {
      if (!_Traits::eq(__str[__i], __zero) && !_Traits::eq(__str[__i], __one))
      {
        _CUDA_VSTD::__throw_invalid_argument("bitset string ctor has invalid argument");
      }
    }

    size_t __mp = _CUDA_VSTD::min(__str.size(), _Size);
    size_t __i  = 0;
    for (; __i < __mp; ++__i)
    {
      _CharT __c   = __str[__mp - 1 - __i];
      (*this)[__i] = _Traits::eq(__c, __one);
    }
    _CUDA_VSTD::fill(base::__make_iter(__i), base::__make_iter(_Size), false);
  }
#else // ^^ _LIBCUDACXX_HAS_STRING_VIEW ^^ | vv !_LIBCUDACXX_HAS_STRING_VIEW vv
  template <class _CharT, class _Traits = char_traits<_CharT>>
  _LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 void
  __init_from_cstr(const _CharT* __str, size_t __size, _CharT __zero, _CharT __one)
  {
    for (size_t __i = 0; __i < __size; ++__i)
    {
      if (!_Traits::eq(__str[__i], __zero) && !_Traits::eq(__str[__i], __one))
      {
        _CUDA_VSTD::__throw_invalid_argument("bitset string ctor has invalid argument");
      }
    }

    size_t __mp = _CUDA_VSTD::min(__size, _Size);
    size_t __i  = 0;
    for (; __i < __mp; ++__i)
    {
      _CharT __c   = __str[__mp - 1 - __i];
      (*this)[__i] = _Traits::eq(__c, __one);
    }
    _CUDA_VSTD::fill(base::__make_iter(__i), base::__make_iter(_Size), false);
  }
#endif // !_LIBCUDACXX_HAS_STRING_VIEW

  _LIBCUDACXX_HIDE_FROM_ABI size_t __hash_code() const noexcept
  {
    return base::__hash_code();
  }

  friend struct hash<bitset>;
};

template <size_t _Size>
_LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bitset<_Size>
operator&(const bitset<_Size>& __x, const bitset<_Size>& __y) noexcept
{
  bitset<_Size> __r = __x;
  __r &= __y;
  return __r;
}

template <size_t _Size>
_LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bitset<_Size>
operator|(const bitset<_Size>& __x, const bitset<_Size>& __y) noexcept
{
  bitset<_Size> __r = __x;
  __r |= __y;
  return __r;
}

template <size_t _Size>
_LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 bitset<_Size>
operator^(const bitset<_Size>& __x, const bitset<_Size>& __y) noexcept
{
  bitset<_Size> __r = __x;
  __r ^= __y;
  return __r;
}

template <size_t _Size>
struct _CCCL_TYPE_VISIBILITY_DEFAULT hash<bitset<_Size>> : public __unary_function<bitset<_Size>, size_t>
{
  _LIBCUDACXX_HIDE_FROM_ABI size_t operator()(const bitset<_Size>& __bs) const noexcept
  {
    return __bs.__hash_code();
  }
};

template <class _CharT, class _Traits, size_t _Size>
_LIBCUDACXX_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Size>& __x);

template <class _CharT, class _Traits, size_t _Size>
_LIBCUDACXX_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Size>& __x);

_LIBCUDACXX_END_NAMESPACE_STD

_CCCL_POP_MACROS

#endif // _CUDA_STD_BITSET