Compiler Explorer

Source code

// ============================== BIT DETAILS =============================== //
// Project:         The C++ Bit Library
// Name:            bit_details.hpp
// Description:     Provides common implementation details and helper classes
// Creator:         Vincent Reverdy
// Contributor(s):  Vincent Reverdy [2015-2017]
// License:         BSD 3-Clause License
// ========================================================================== //
#ifndef _BIT_DETAILS_HPP_INCLUDED
#define _BIT_DETAILS_HPP_INCLUDED
// ========================================================================== //

// ================================ PREAMBLE ================================ //
// C++ standard library
#include <tuple>
#include <limits>
#include <cassert>
#include <cstdint>
#include <utility>
#include <iterator>
#include <algorithm>
#include <stdexcept>
#include <type_traits>
// Project sources
// Third-party libraries
// Miscellaneous
namespace bit {
class bit_value;
template <class WordType> class bit_reference;
template <class WordType> class bit_pointer;
template <class Iterator> class bit_iterator;
// ========================================================================== //

/* ***************************** BINARY DIGITS ****************************** */
// Binary digits structure definition
template <class UIntType>
struct binary_digits 
: std::conditional<
 std::is_const<UIntType>::value || std::is_volatile<UIntType>::value,
 binary_digits<typename std::remove_cv<UIntType>::type>,
 std::integral_constant<std::size_t, std::numeric_limits<UIntType>::digits>
>::type
{
 // Assertions
 static_assert(std::is_integral<UIntType>::value, "");
 static_assert(std::is_unsigned<UIntType>::value, "");
 static_assert(!std::is_same<UIntType, bool>::value, "");
 static_assert(!std::is_same<UIntType, char>::value, "");
};

// Binary digits value
template <class T>
constexpr std::size_t binary_digits_v = binary_digits<T>::value;
/* ************************************************************************** */

/* *************** IMPLEMENTATION DETAILS: CV ITERATOR TRAITS *************** */
// Cv iterator traits structure definition
template <class Iterator>
struct _cv_iterator_traits
{
 // Assertions
 private:
 using _traits_t = std::iterator_traits<Iterator>;
 using _difference_t = typename _traits_t::difference_type;
 using _value_t = typename _traits_t::value_type;
 using _pointer_t = typename _traits_t::pointer;
 using _reference_t = typename _traits_t::reference;
 using _category_t = typename _traits_t::iterator_category;
 using _no_pointer_t = typename std::remove_pointer<_pointer_t>::type;
 using _no_reference_t = typename std::remove_reference<_reference_t>::type;
 using _raw_value_t = typename std::remove_cv<_value_t>::type;
 using _raw_pointer_t = typename std::remove_cv<_no_pointer_t>::type;
 using _raw_reference_t = typename std::remove_cv<_no_reference_t>::type;
 using _cv_value_t = _no_reference_t;
 static_assert(std::is_same<_raw_pointer_t, _raw_value_t>::value, "");
 static_assert(std::is_same<_raw_reference_t, _raw_value_t>::value, "");
 
 // Types
 public:
 using difference_type = _difference_t;
 using value_type = _cv_value_t;
 using pointer = _pointer_t;
 using reference = _reference_t;
 using iterator_category = _category_t;
};
/* ************************************************************************** */

/* *********** IMPLEMENTATION DETAILS: NARROWEST AND WIDEST TYPES *********** */
// Narrowest type structure declaration
template <class... T>
struct _narrowest_type;

// Narrowest type structure specialization: selects the only passed type
template <class T>
struct _narrowest_type<T>
: std::common_type<T>
{
 static_assert(binary_digits<T>::value, "");
};

// Narrowest type structure specialization: selects the type with less bits
template <class T, class U>
struct _narrowest_type<T, U>
: _narrowest_type<
 typename std::conditional<
 (binary_digits<T>::value < binary_digits::value),
 T,
 typename std::conditional<
 (binary_digits<T>::value > binary_digits::value),
 U,
 typename std::common_type<T, U>::type
 >::type
 >::type
>
{
};

// Narrowest type structure specialization: recursively selects the right type
template <class T, class... U>
struct _narrowest_type<T, U...>
: _narrowest_type<T, typename _narrowest_type<U...>::type>
{
};

// Narrowest type alias
template <class... T>
using _narrowest_type_t = typename _narrowest_type<T...>::type;

// Widest type structure declaration
template <class... X>
struct _widest_type;

// Widest type structure specialization: selects the only passed type
template <class T>
struct _widest_type<T>
: std::common_type<T>
{
 static_assert(binary_digits<T>::value, "");
};

// Widest type structure specialization: selects the type with more bits
template <class T, class U>
struct _widest_type<T, U>
: _widest_type<
 typename std::conditional<
 (binary_digits<T>::value > binary_digits::value),
 T,
 typename std::conditional<
 (binary_digits<T>::value < binary_digits::value),
 U,
 typename std::common_type<T, U>::type
 >::type
 >::type
>
{
};

// Widest type structure specialization: recursively selects the right type
template <class T, class... X>
struct _widest_type<T, X...>
: _widest_type<T, typename _widest_type<X...>::type>
{
};

// Widest type alias
template <class... T>
using _widest_type_t = typename _widest_type<T...>::type;
/* ************************************************************************** */

/* ************ IMPLEMENTATION DETAILS: NARROWER AND WIDER TYPES ************ */
// Narrower type structure definition
template <class T, int I = 0>
struct _narrower_type
{
 using tuple = std::tuple<
 unsigned long long int,
 unsigned long int,
 unsigned int,
 unsigned short int,
 unsigned char
 >;
 using lhs_bits = binary_digits<T>;
 using rhs_bits = binary_digits<typename std::tuple_element<I, tuple>::type>;
 using type = typename std::conditional<
 (lhs_bits::value > rhs_bits::value),
 typename std::tuple_element<I, tuple>::type,
 typename std::conditional<
 (I + 1 < std::tuple_size<tuple>::value),
 typename _narrower_type<
 T,
 (I + 1 < std::tuple_size<tuple>::value ? I + 1 : -1)
 >::type,
 typename std::tuple_element<I, tuple>::type
 >::type
 >::type;
};

// Narrower type structure specialization: not found
template <class T>
struct _narrower_type<T, -1>
{
 using type = T;
};

// Narrower type alias
template <class T>
using _narrower_type_t = typename _narrower_type<T>::type;

// Wider type structure definition
template <class T, int I = 0>
struct _wider_type
{
 using tuple = std::tuple<
 unsigned char,
 unsigned short int,
 unsigned int,
 unsigned long int,
 unsigned long long int
 >;
 using lhs_bits = binary_digits<T>;
 using rhs_bits = binary_digits<typename std::tuple_element<I, tuple>::type>;
 using type = typename std::conditional<
 (lhs_bits::value < rhs_bits::value),
 typename std::tuple_element<I, tuple>::type,
 typename std::conditional<
 (I + 1 < std::tuple_size<tuple>::value),
 typename _narrower_type<
 T,
 (I + 1 < std::tuple_size<tuple>::value ? I + 1 : -1)
 >::type,
 typename std::tuple_element<I, tuple>::type
 >::type
 >::type;
};

// Wider type structure specialization: not found
template <class T>
struct _wider_type<T, -1>
{
 using type = T;
};

// Wider type alias
template <class T>
using _wider_type_t = typename _wider_type<T>::type;
/* ************************************************************************** */

/* ******************* IMPLEMENTATION DETAILS: UTILITIES ******************** */
// Assertions
template <class Iterator>
constexpr bool _assert_range_viability(Iterator first, Iterator last);
/* ************************************************************************** */

/* ****************** IMPLEMENTATION DETAILS: INSTRUCTIONS ****************** */
// Population count
template <class T, class = decltype(__builtin_popcountll(T()))>
constexpr T _popcnt(T src) noexcept;
template <class T, class... X>
constexpr T _popcnt(T src, X...) noexcept;

// Leading zeros count
template <class T, class = decltype(__builtin_clzll(T()))>
constexpr T _lzcnt(T src) noexcept;
template <class T, class... X>
constexpr T _lzcnt(T src, X...) noexcept;

// Trailing zeros count
template <class T, class = decltype(__builtin_ctzll(T()))>
constexpr T _tzcnt(T src) noexcept;
template <class T, class... X>
constexpr T _tzcnt(T src, X...) noexcept;

// Bit field extraction
template <class T, class = decltype(__builtin_ia32_bextr_u64(T(), T(), T()))>
constexpr T _bextr(T src, T start, T len) noexcept;
template <class T, class... X>
constexpr T _bextr(T src, T start, T len, X...) noexcept;

// Parallel bits deposit
template <class T, class = decltype(_pdep_u64(T()))>
constexpr T _pdep(T src, T msk) noexcept;
template <class T, class... X>
constexpr T _pdep(T src, T msk, X...) noexcept;

// Parallel bits extract
template <class T, class = decltype(_pext_u64(T()))>
constexpr T _pext(T src, T msk) noexcept;
template <class T, class... X>
constexpr T _pext(T src, T msk, X...) noexcept;

// Byte swap
template <class T, class T128 = decltype(__uint128_t(__builtin_bswap64(T())))>
constexpr T _byteswap(T src) noexcept;
template <class T, class... X>
constexpr T _byteswap(T src, X...) noexcept;

// Bit swap
template <class T>
constexpr T _bitswap(T src) noexcept;
template <class T, std::size_t N>
constexpr T _bitswap(T src) noexcept;
template <class T, std::size_t N>
constexpr T _bitswap() noexcept;

// Bit blend
template <class T>
constexpr T _bitblend(T src0, T src1, T msk) noexcept;
template <class T>
constexpr T _bitblend(T src0, T src1, T start, T len) noexcept;

// Bit compare
template <class T>
constexpr T _bitcmp(T src0, T src1, T start0, T start1, T len) noexcept;

// Double precision shift left
template <class T>
constexpr T _shld(T dst, T src, T cnt) noexcept;

// Double precision shift right
template <class T>
constexpr T _shrd(T dst, T src, T cnt) noexcept;

// Add carry
template <class... T>
using _supports_adc = decltype(__builtin_ia32_addcarryx_u64(T()...));
template <class C, class T, class = _supports_adc<C, T, T, std::nullptr_t>>
constexpr C _addcarry(C carry, T src0, T src1, T* dst) noexcept;
template <class C, class T, class... X>
constexpr C _addcarry(C carry, T src0, T src1, T* dst, X...) noexcept;

// Sub borrow
template <class... T>
using _supports_sbb = decltype(__builtin_ia32_sbb_u64(T()...));
template <class... T>
using _supports_sbb_alt = decltype(__builtin_ia32_subborrow_u64(T()...));
template <class B, class T, class = _supports_sbb<B, T, T, std::nullptr_t>>
constexpr B _subborrow(B borrow, T src0, T src1, T* dst) noexcept;
template <class B, class T, class = _supports_sbb_alt<B, T, T, std::nullptr_t>>
constexpr B _subborrow(const B& borrow, T src0, T src1, T* dst) noexcept;
template <class B, class T, class... X>
constexpr B _subborrow(B borrow, T src0, T src1, T* dst, X...) noexcept;

// Multiword multiply
template <class T, class T128 = decltype(__uint128_t(T()))>
constexpr T _mulx(T src0, T src1, T* hi) noexcept;
template <class T, class... X>
constexpr T _mulx(T src0, T src1, T* hi, X...) noexcept;
/* ************************************************************************** */

// ------------- IMPLEMENTATION DETAILS: UTILITIES: ASSERTIONS -------------- //
// If the range allows multipass iteration, checks if last - first >= 0
template <class Iterator>
constexpr bool _assert_range_viability(Iterator first, Iterator last)
{
 using traits_t = std::iterator_traits<Iterator>;
 using category_t = typename traits_t::iterator_category;
 using multi_t = std::forward_iterator_tag;
 constexpr bool is_multipass = std::is_base_of<multi_t, category_t>::value;
 const bool is_viable = !is_multipass || std::distance(first, last) >= 0;
 assert(is_viable);
 return is_viable;
}
// -------------------------------------------------------------------------- //

// --------- IMPLEMENTATION DETAILS: INSTRUCTIONS: POPULATION COUNT --------- //
// Counts the number of bits set to 1 with compiler intrinsics
template <class T, class>
constexpr T _popcnt(T src) noexcept
{
 static_assert(binary_digits<T>::value, "");
 constexpr T digits = binary_digits<T>::value;
 if (digits <= std::numeric_limits<unsigned int>::digits) {
 src = __builtin_popcount(src); 
 } else if (digits <= std::numeric_limits<unsigned long int>::digits) {
 src = __builtin_popcountl(src); 
 } else if (digits <= std::numeric_limits<unsigned long long int>::digits) {
 src = __builtin_popcountll(src); 
 } else {
 src = _popcnt(src, std::ignore);
 }
 return src;
}

// Counts the number of bits set to 1 without compiler intrinsics
template <class T, class... X>
constexpr T _popcnt(T src, X...) noexcept
{
 static_assert(binary_digits<T>::value, "");
 T dst = T();
 for (dst = T(); src; src >>= 1) {
 dst += src & 1;
 }
 return dst;
}
// -------------------------------------------------------------------------- //

// ------- IMPLEMENTATION DETAILS: INSTRUCTIONS: LEADING ZEROS COUNT -------- //
// Counts the number of leading zeros with compiler intrinsics
template <class T, class>
constexpr T _lzcnt(T src) noexcept
{
 static_assert(binary_digits<T>::value, "");
 constexpr T digits = binary_digits<T>::value;
 T dst = T();
 if (digits < std::numeric_limits<unsigned int>::digits) {
 dst = src ? __builtin_clz(src)
 - (std::numeric_limits<unsigned int>::digits 
 - digits)
 : digits;
 } else if (digits == std::numeric_limits<unsigned int>::digits) {
 dst = src ? __builtin_clz(src) : digits;
 } else if (digits < std::numeric_limits<unsigned long int>::digits) {
 dst = src ? __builtin_clzl(src)
 - (std::numeric_limits<unsigned long int>::digits 
 - digits)
 : digits;
 } else if (digits == std::numeric_limits<unsigned long int>::digits) {
 dst = src ? __builtin_clzl(src) : digits;
 } else if (digits < std::numeric_limits<unsigned long long int>::digits) {
 dst = src ? __builtin_clzll(src)
 - (std::numeric_limits<unsigned long long int>::digits 
 - digits)
 : digits;
 } else if (digits == std::numeric_limits<unsigned long long int>::digits) {
 dst = src ? __builtin_clzll(src) : digits;
 } else {
 dst = _lzcnt(src, std::ignore);
 }
 return dst;
}

// Counts the number of leading zeros without compiler intrinsics
template <class T, class... X>
constexpr T _lzcnt(T src, X...) noexcept
{
 static_assert(binary_digits<T>::value, "");
 constexpr T digits = binary_digits<T>::value;
 T dst = src != T();
 while (src >>= 1) {
 ++dst;
 }
 return digits - dst;
}
// -------------------------------------------------------------------------- //

// ------- IMPLEMENTATION DETAILS: INSTRUCTIONS: TRAILING ZEROS COUNT ------- //
// Counts the number of trailing zeros with compiler intrinsics
template <class T, class>
constexpr T _tzcnt(T src) noexcept
{
 static_assert(binary_digits<T>::value, "");
 constexpr T digits = binary_digits<T>::value;
 T dst = T();
 if (digits <= std::numeric_limits<unsigned int>::digits) {
 dst = src ? __builtin_ctz(src) : digits; 
 } else if (digits <= std::numeric_limits<unsigned long int>::digits) {
 dst = src ? __builtin_ctzl(src) : digits; 
 } else if (digits <= std::numeric_limits<unsigned long long int>::digits) {
 dst = src ? __builtin_ctzll(src) : digits; 
 } else {
 dst = _tzcnt(src, std::ignore);
 }
 return dst;
}

// Counts the number of trailing zeros without compiler intrinsics
template <class T, class... X>
constexpr T _tzcnt(T src, X...) noexcept
{
 static_assert(binary_digits<T>::value, "");
 constexpr T digits = binary_digits<T>::value;
 T dst = digits;
 if (src) {
 src = (src ^ (src - 1)) >> 1;
 for (dst = T(); src; dst++) {
 src >>= 1;
 }
 }
 return dst;
}
// -------------------------------------------------------------------------- //

// ------- IMPLEMENTATION DETAILS: INSTRUCTIONS: BIT FIELD EXTRACTION ------- //
// Extacts to lsbs a field of contiguous bits with compiler intrinsics
template <class T, class>
constexpr T _bextr(T src, T start, T len) noexcept
{
 static_assert(binary_digits<T>::value, "");
 constexpr T digits = binary_digits<T>::value;
 T dst = T();
 if (digits <= std::numeric_limits<unsigned int>::digits) {
 dst = __builtin_ia32_bextr_u32(src, start, len); 
 } else if (digits <= std::numeric_limits<unsigned long long int>::digits) {
 dst = __builtin_ia32_bextr_u64(src, start, len);
 } else {
 dst = _bextr(src, start, len, std::ignore);
 }
 return dst;
}

// Extacts to lsbs a field of contiguous bits without compiler intrinsics
template <class T, class... X>
constexpr T _bextr(T src, T start, T len, X...) noexcept
{
 static_assert(binary_digits<T>::value, "");
 constexpr T digits = binary_digits<T>::value;
 constexpr T one = 1;
 const T msk = (one << len) * (len < digits) - one;
 return (src >> start) & msk * (start < digits);
}
// -------------------------------------------------------------------------- //

// ------- IMPLEMENTATION DETAILS: INSTRUCTIONS: PARALLEL BIT DEPOSIT ------- //
// Deposits bits according to a mask with compiler instrinsics
template <class T, class>
constexpr T _pdep(T src, T msk) noexcept
{
 static_assert(binary_digits<T>::value, "");
 constexpr T digits = binary_digits<T>::value;
 T dst = T();
 if (digits <= std::numeric_limits<unsigned int>::digits) {
 dst = _pdep_u32(src, msk); 
 } else if (digits <= std::numeric_limits<unsigned long long int>::digits) {
 dst = _pdep_u64(src, msk);
 } else {
 dst = _pdep(src, msk, std::ignore);
 }
 return dst;
}

// Deposits bits according to a mask without compiler instrinsics
template <class T, class... X>
constexpr T _pdep(T src, T msk, X...) noexcept
{
 static_assert(binary_digits<T>::value, "");
 constexpr T digits = binary_digits<T>::value;
 T dst = T();
 T cnt = T();
 while (msk) {
 dst >>= 1;
 if (msk & 1) {
 dst |= src << (digits - 1);
 src >>= 1;
 }
 msk >>= 1;
 ++cnt;
 }
 dst >>= (digits - cnt) * (cnt > 0);
 return dst;
}
// -------------------------------------------------------------------------- //

// ------- IMPLEMENTATION DETAILS: INSTRUCTIONS: PARALLEL BIT EXTRACT ------- //
// Extracts bits according to a mask with compiler instrinsics
template <class T, class>
constexpr T _pext(T src, T msk) noexcept
{
 static_assert(binary_digits<T>::value, "");
 constexpr T digits = binary_digits<T>::value;
 T dst = T();
 if (digits <= std::numeric_limits<unsigned int>::digits) {
 dst = _pext_u32(src, msk); 
 } else if (digits <= std::numeric_limits<unsigned long long int>::digits) {
 dst = _pext_u64(src, msk);
 } else {
 dst = _pext(src, msk, std::ignore);
 }
 return dst;
}

// Extracts bits according to a mask without compiler instrinsics
template <class T, class... X>
constexpr T _pext(T src, T msk, X...) noexcept
{
 static_assert(binary_digits<T>::value, "");
 constexpr T digits = binary_digits<T>::value;
 T dst = T();
 T cnt = T();
 while (msk) {
 if (msk & 1) {
 dst >>= 1;
 dst |= src << (digits - 1);
 ++cnt;
 }
 src >>= 1;
 msk >>= 1;
 }
 dst >>= (digits - cnt) * (cnt > 0);
 return dst;
}
// -------------------------------------------------------------------------- //

// ------------ IMPLEMENTATION DETAILS: INSTRUCTIONS: BYTE SWAP ------------- //
// Reverses the order of the underlying bytes with compiler intrinsics
template <class T, class T128>
constexpr T _byteswap(T src) noexcept
{
 static_assert(binary_digits<T>::value, "");
 using byte_t = unsigned char;
 constexpr T digits = sizeof(T) * std::numeric_limits<byte_t>::digits;
 std::uint64_t tmp64 = 0;
 std::uint64_t* ptr64 = nullptr;
 if (std::is_same<T, T128>::value) {
 ptr64 = reinterpret_cast<std::uint64_t*>(&src);
 tmp64 = __builtin_bswap64(*ptr64);
 *ptr64 = __builtin_bswap64(*(ptr64 + 1));
 *(ptr64 + 1) = tmp64;
 } else if (digits == std::numeric_limits<std::uint16_t>::digits) {
 src = __builtin_bswap16(src);
 } else if (digits == std::numeric_limits<std::uint32_t>::digits) {
 src = __builtin_bswap32(src);
 } else if (digits == std::numeric_limits<std::uint64_t>::digits) {
 src = __builtin_bswap64(src);
 } else if (digits > std::numeric_limits<byte_t>::digits) {
 src = _byteswap(src, std::ignore);
 }
 return src;
}

// Reverses the order of the underlying bytes without compiler intrinsics
template <class T, class... X>
constexpr T _byteswap(T src, X...) noexcept
{
 static_assert(binary_digits<T>::value, "");
 using byte_t = unsigned char;
 constexpr T half = sizeof(T) / 2;
 constexpr T end = sizeof(T) - 1;
 unsigned char* bytes = reinterpret_cast<byte_t*>(&src);
 unsigned char byte = 0;
 for (T i = T(); i < half; ++i) {
 byte = bytes[i];
 bytes[i] = bytes[end - i];
 bytes[end - i] = byte;
 }
 return src;
}
// -------------------------------------------------------------------------- //

// ------------- IMPLEMENTATION DETAILS: INSTRUCTIONS: BIT SWAP ------------- //
// Reverses the order of the bits with or without of compiler intrinsics
template <class T>
constexpr T _bitswap(T src) noexcept
{
 static_assert(binary_digits<T>::value, "");
 using byte_t = unsigned char;
 constexpr auto ignore = nullptr;
 constexpr T digits = binary_digits<T>::value;
 constexpr unsigned long long int first = 0x80200802ULL;
 constexpr unsigned long long int second = 0x0884422110ULL;
 constexpr unsigned long long int third = 0x0101010101ULL;
 constexpr unsigned long long int fourth = 32;
 constexpr bool is_size1 = sizeof(T) == 1;
 constexpr bool is_byte = digits == std::numeric_limits<byte_t>::digits;
 constexpr bool is_octet = std::numeric_limits<byte_t>::digits == 8;
 constexpr bool is_pow2 = _popcnt(digits, ignore) == 1;
 T dst = src;
 T i = digits - 1;
 if (is_size1 && is_byte && is_octet) {
 dst = ((src * first) & second) * third >> fourth;
 } else if (is_pow2) {
 dst = _bitswap<T, digits>(src);
 } else {
 for (src >>= 1; src; src >>= 1) { 
 dst <<= 1;
 dst |= src & 1;
 i--;
 }
 dst <<= i;
 }
 return dst;
}

// Reverses the order of the bits: recursive metafunction
template <class T, std::size_t N>
constexpr T _bitswap(T src) noexcept
{
 static_assert(binary_digits<T>::value, "");
 constexpr T cnt = N >> 1;
 constexpr T msk = _bitswap<T, cnt>();
 src = ((src >> cnt) & msk) | ((src << cnt) & ~msk);
 return cnt > 1 ? _bitswap<T, cnt>(src) : src;
}

// Reverses the order of the bits: mask for the recursive metafunction
template <class T, std::size_t N>
constexpr T _bitswap() noexcept
{
 static_assert(binary_digits<T>::value, "");
 constexpr T digits = binary_digits<T>::value;
 T cnt = digits;
 T msk = ~T();
 while (cnt != N) {
 cnt >>= 1;
 msk ^= (msk << cnt);
 }
 return msk;
}
// -------------------------------------------------------------------------- //

// ------------ IMPLEMENTATION DETAILS: INSTRUCTIONS: BIT BLEND ------------- //
// Replaces len bits of src0 by the ones of src1 where the mask is true
template <class T>
constexpr T _bitblend(T src0, T src1, T msk) noexcept
{
 static_assert(binary_digits<T>::value, "");
 return src0 ^ ((src0 ^ src1) & msk);
}

// Replaces len bits of src0 by the ones of src1 starting at start
template <class T>
constexpr T _bitblend(T src0, T src1, T start, T len) noexcept
{
 static_assert(binary_digits<T>::value, "");
 constexpr T digits = binary_digits<T>::value;
 constexpr T one = 1;
 const T msk = ((one << len) * (len < digits) - one) << start;
 return src0 ^ ((src0 ^ src1) & msk * (start < digits));
}
// -------------------------------------------------------------------------- //

// ----------- IMPLEMENTATION DETAILS: INSTRUCTIONS: BIT COMPARE ------------ //
// Compares a subsequence of bits within src0 and src1 and returns 0 if equal
template <class T>
constexpr T _bitcmp(T src0, T src1, T start0, T start1, T len) noexcept
{
 static_assert(binary_digits<T>::value, "");
 return _bextr(src0, start0, len) == _bextr(src1, start1, len);
}
// -------------------------------------------------------------------------- //

// --- IMPLEMENTATION DETAILS: INSTRUCTIONS: DOUBLE PRECISION SHIFT LEFT ---- //
// Left shifts dst by cnt bits, filling the lsbs of dst by the msbs of src
template <class T>
constexpr T _shld(T dst, T src, T cnt) noexcept
{
 static_assert(binary_digits<T>::value, "");
 constexpr T digits = binary_digits<T>::value;
 if (cnt < digits) {
 dst = (dst << cnt) | (src >> (digits - cnt));
 } else {
 dst = (src << (cnt - digits)) * (cnt < digits + digits);
 }
 return dst;
}
// -------------------------------------------------------------------------- //

// --- IMPLEMENTATION DETAILS: INSTRUCTIONS: DOUBLE PRECISION SHIFT RIGHT --- //
// Right shifts dst by cnt bits, filling the msbs of dst by the lsbs of src
template <class T>
constexpr T _shrd(T dst, T src, T cnt) noexcept
{
 static_assert(binary_digits<T>::value, "");
 constexpr T digits = binary_digits<T>::value;
 if (cnt < digits) {
 dst = (dst >> cnt) | (src << (digits - cnt));
 } else {
 dst = (src >> (cnt - digits)) * (cnt < digits + digits);
 }
 return dst;
}
// -------------------------------------------------------------------------- //

// ------------ IMPLEMENTATION DETAILS: INSTRUCTIONS: ADD CARRY ------------- //
// Adds src0 and src1 and returns the new carry bit with intrinsics
template <class C, class T, class>
constexpr C _addcarry(C carry, T src0, T src1, T* dst) noexcept
{
 static_assert(binary_digits<T>::value, "");
 using wider_t = typename _wider_type<T>::type;
 constexpr T digits = binary_digits<T>::value;
 wider_t tmp = 0;
 unsigned int udst = 0;
 unsigned long long int ulldst = 0;
 if (digits == std::numeric_limits<unsigned int>::digits) {
 carry = __builtin_ia32_addcarryx_u32(carry, src0, src1, &udst);
 *dst = udst;
 } else if (digits == std::numeric_limits<unsigned long long int>::digits) {
 carry = __builtin_ia32_addcarryx_u64(carry, src0, src1, &ulldst);
 *dst = ulldst;
 } else if (digits < binary_digits<wider_t>::value) {
 tmp = static_cast<wider_t>(src0) + static_cast<wider_t>(src1);
 tmp += static_cast<wider_t>(static_cast<bool>(carry));
 *dst = tmp;
 carry = static_cast<bool>(tmp >> digits);
 } else {
 carry = _addcarry(carry, src0, src1, dst, std::ignore);
 }
 return carry;
}

// Adds src0 and src1 and returns the new carry bit without intrinsics
template <class C, class T, class... X>
constexpr C _addcarry(C carry, T src0, T src1, T* dst, X...) noexcept
{
 static_assert(binary_digits<T>::value, "");
 *dst = src0 + src1 + static_cast<T>(static_cast<bool>(carry));
 return carry ? *dst <= src0 || *dst <= src1 : *dst < src0 || *dst < src1;
}
// -------------------------------------------------------------------------- //

// ------------ IMPLEMENTATION DETAILS: INSTRUCTIONS: SUB BORROW ------------ //
// Subtracts src1 to src0 and returns the new borrow bit with intrinsics
template <class B, class T, class>
constexpr B _subborrow(B borrow, T src0, T src1, T* dst) noexcept
{
 static_assert(binary_digits<T>::value, "");
 using wider_t = typename _wider_type<T>::type;
 constexpr T digits = binary_digits<T>::value;
 wider_t tmp = 0;
 unsigned int udst = 0;
 unsigned long long int ulldst = 0;
 if (digits == std::numeric_limits<unsigned int>::digits) {
 borrow = __builtin_ia32_sbb_u32(borrow, src0, src1, &udst);
 *dst = udst;
 } else if (digits == std::numeric_limits<unsigned long long int>::digits) {
 borrow = __builtin_ia32_sbb_u64(borrow, src0, src1, &ulldst);
 *dst = ulldst;
 } else if (digits < binary_digits<wider_t>::value) {
 tmp = static_cast<wider_t>(src1);
 tmp += static_cast<wider_t>(static_cast<bool>(borrow));
 borrow = tmp > static_cast<wider_t>(src0);
 *dst = static_cast<wider_t>(src0) - tmp;
 } else {
 borrow = _subborrow(borrow, src0, src1, dst, std::ignore);
 }
 return borrow;
}

// Subtracts src1 to src0 and returns the new borrow bit with other intrinsics
template <class B, class T, class>
constexpr B _subborrow(const B& borrow, T src0, T src1, T* dst) noexcept
{
 static_assert(binary_digits<T>::value, "");
 using wider_t = typename _wider_type<T>::type;
 constexpr T digits = binary_digits<T>::value;
 wider_t tmp = 0;
 unsigned int udst = 0;
 unsigned long long int ulldst = 0;
 B flag = borrow;
 if (digits == std::numeric_limits<unsigned int>::digits) {
 flag = __builtin_ia32_subborrow_u32(borrow, src0, src1, &udst);
 *dst = udst;
 } else if (digits == std::numeric_limits<unsigned long long int>::digits) {
 flag = __builtin_ia32_subborrow_u64(borrow, src0, src1, &ulldst);
 *dst = ulldst;
 } else if (digits < binary_digits<wider_t>::value) {
 tmp = static_cast<wider_t>(src1);
 tmp += static_cast<wider_t>(static_cast<bool>(borrow));
 flag = tmp > static_cast<wider_t>(src0);
 *dst = static_cast<wider_t>(src0) - tmp;
 } else {
 flag = _subborrow(borrow, src0, src1, dst, std::ignore);
 }
 return flag;
}

// Subtracts src1 to src0 and returns the new borrow bit without intrinsics
template <class B, class T, class... X>
constexpr B _subborrow(B borrow, T src0, T src1, T* dst, X...) noexcept
{
 static_assert(binary_digits<T>::value, "");
 *dst = src0 - (src1 + static_cast<T>(static_cast<bool>(borrow)));
 return borrow ? src1 >= src0 : src1 > src0;
}
// -------------------------------------------------------------------------- //

// -------- IMPLEMENTATION DETAILS: INSTRUCTIONS: MULTIWORD MULTIPLY -------- //
// Multiplies src0 and src1 and gets the full result with compiler intrinsics
template <class T, class T128>
constexpr T _mulx(T src0, T src1, T* hi) noexcept
{
 static_assert(binary_digits<T>::value, "");
 using wider_t = typename _wider_type<T>::type;
 constexpr T digits = binary_digits<T>::value;
 wider_t tmp = 0;
 T128 tmp128 = 0;
 T lo = 0;
 if (digits == std::numeric_limits<std::uint64_t>::digits) {
 tmp128 = static_cast<T128>(src0) * static_cast<T128>(src1);
 *hi = tmp128 >> digits;
 lo = tmp128;
 } else if (digits + digits == binary_digits<wider_t>::value) {
 tmp = static_cast<wider_t>(src0) * static_cast<wider_t>(src1);
 *hi = tmp >> digits;
 lo = tmp;
 } else {
 lo = _mulx(src0, src1, hi, std::ignore);
 }
 return lo;
}

// Multiplies src0 and src1 and gets the full result without compiler intrinsics
template <class T, class... X>
constexpr T _mulx(T src0, T src1, T* hi, X...) noexcept
{
 static_assert(binary_digits<T>::value, "");
 constexpr T digits = binary_digits<T>::value;
 constexpr T offset = digits / 2;
 constexpr T ones = ~static_cast<T>(0);
 const T lsbs0 = src0 & static_cast<T>(ones >> (digits - offset));
 const T msbs0 = src0 >> offset;
 const T lsbs1 = src1 & static_cast<T>(ones >> (digits - offset));
 const T msbs1 = src1 >> offset;
 const T llsbs = lsbs0 * lsbs1;
 const T mlsbs = msbs0 * lsbs1;
 const T lmsbs = lsbs0 * msbs1;
 const T mi = mlsbs + lmsbs;
 const T lo = llsbs + static_cast<T>(mi << offset);
 const T lcarry = lo < llsbs || lo < static_cast<T>(mi << offset);
 const T mcarry = static_cast<T>(mi < mlsbs || mi < lmsbs) << offset;
 *hi = static_cast<T>(mi >> offset) + msbs0 * msbs1 + mcarry + lcarry;
 return lo;
}
// -------------------------------------------------------------------------- //

// ========================================================================== //
} // namespace bit
#endif // _BIT_DETAILS_HPP_INCLUDED
// ========================================================================== //

// =============================== BIT VALUE ================================ //
// Project:         The C++ Bit Library
// Name:            bit_value.hpp
// Description:     A class representing an independent, non-referenced bit
// Creator:         Vincent Reverdy
// Contributor(s):  Vincent Reverdy [2015-2017]
// License:         BSD 3-Clause License
// ========================================================================== //
#ifndef _BIT_VALUE_HPP_INCLUDED
#define _BIT_VALUE_HPP_INCLUDED
// ========================================================================== //

// ================================ PREAMBLE ================================ //
// C++ standard library
// Project sources
//#include "bit_details.hpp"
// Third-party libraries
// Miscellaneous
namespace bit {
// ========================================================================== //

/* ******************************* BIT VALUE ******************************** */
// Bit value class definition
class bit_value
{
 // Friendship
 template <class> friend class bit_reference;
 
 // Types
 public:
 using size_type = std::size_t;
 
 // Lifecycle
 public:
 constexpr bit_value() noexcept;
 template <class T> 
 constexpr bit_value(bit_reference<T> ref) noexcept;
 template <class WordType> 
 explicit constexpr bit_value(WordType val) noexcept;
 template <class WordType> 
 constexpr bit_value(WordType val, size_type pos);
 
 // Assignment
 public:
 template <class T> 
 constexpr bit_value& operator=(bit_reference<T> ref) noexcept;
 template <class WordType> 
 constexpr bit_value& assign(WordType val) noexcept;
 template <class WordType> 
 constexpr bit_value& assign(WordType val, size_type pos);

// Bitwise assignment operators
    public:
    constexpr bit_value& operator&=(bit_value other) noexcept;
    constexpr bit_value& operator|=(bit_value other) noexcept;
    constexpr bit_value& operator^=(bit_value other) noexcept;

// Conversion
 public:
 explicit constexpr operator bool() const noexcept;
 
 // Swap members
 public:
 void swap(bit_value& other) noexcept;
 template <class T> 
 void swap(bit_reference<T> other) noexcept;

// Bit manipulation
    public:
    constexpr bit_value& set(bool b) noexcept;
    constexpr bit_value& set() noexcept;
    constexpr bit_value& reset() noexcept;
    constexpr bit_value& flip() noexcept;

// Implementation details: data members
    private:
    bool _value;
    
    // Bitwise operators
    public:
    friend constexpr bit_value operator~(
        bit_value rhs
    ) noexcept;
    friend constexpr bit_value operator&(
        bit_value lhs, 
        bit_value rhs
    ) noexcept;
    friend constexpr bit_value operator|(
        bit_value lhs, 
        bit_value rhs
    ) noexcept;
    friend constexpr bit_value operator^(
        bit_value lhs, 
        bit_value rhs
    ) noexcept;

// Comparison operators
 public:
 friend constexpr bool operator==(
 bit_value lhs, 
 bit_value rhs
 ) noexcept;
 friend constexpr bool operator!=(
 bit_value lhs, 
 bit_value rhs
 ) noexcept;
 friend constexpr bool operator<(
 bit_value lhs, 
 bit_value rhs
 ) noexcept;
 friend constexpr bool operator<=(
 bit_value lhs, 
 bit_value rhs
 ) noexcept;
 friend constexpr bool operator>(
 bit_value lhs, 
 bit_value rhs
 ) noexcept;
 friend constexpr bool operator>=(
 bit_value lhs, 
 bit_value rhs
 ) noexcept;
};

// Stream functions
template <class CharT, class Traits>
std::basic_istream<CharT, Traits>& operator>>(
 std::basic_istream<CharT, Traits>& is,
 bit_value& x
);
template <class CharT, class Traits>
std::basic_ostream<CharT, Traits>& operator<<(
 std::basic_ostream<CharT, Traits>& os,
 bit_value x
);

// Constants
/* ************************************************************************** */

// -------------------------- BIT VALUE: LIFECYCLE -------------------------- //
// Implicitly default constructs a bit value initialized to zero
constexpr bit_value::bit_value(
) noexcept
: _value(false)
{
}

// Implicitly constructs a bit value from a bit reference
template <class T> 
constexpr bit_value::bit_value(
 bit_reference<T> ref
) noexcept
: _value(static_cast<bool>(ref))
{
}
 
// Explicitly constructs an aligned bit value
template <class WordType>
constexpr bit_value::bit_value(
 WordType val
) noexcept
: _value(val & 1)
{
 static_assert(binary_digits<WordType>::value, "");
}

// Explicitly constructs an unaligned bit value
template <class WordType> 
constexpr bit_value::bit_value(
 WordType val, 
 size_type pos
)
: _value((assert(pos < binary_digits<WordType>::value), val >> pos & 1))
{
 static_assert(binary_digits<WordType>::value, "");
}
// -------------------------------------------------------------------------- //

// ------------------------- BIT VALUE: ASSIGNMENT -------------------------- //
// Assigns a bit reference to the bit value
template <class T> 
constexpr bit_value& bit_value::operator=(
 bit_reference<T> ref
) noexcept
{
 _value = static_cast<bool>(ref);
 return *this;
}

// Assigns the aligned bit of a value to the bit value
template <class WordType> 
constexpr bit_value& bit_value::assign(
 WordType val
) noexcept
{
 static_assert(binary_digits<WordType>::value, "");
 _value = val & 1;
 return *this;
}

// Assigns an unaligned bit of a value to the bit value
template <class WordType> 
constexpr bit_value& bit_value::assign(
 WordType val, 
 size_type pos
)
{
 assert(pos < binary_digits<WordType>::value);
 _value = val >> pos & 1;
 return *this;
}
// -------------------------------------------------------------------------- //

// ---------------- BIT VALUE: BITWISE ASSIGNMENT OPERATORS ----------------- //
// Assigns the value of the bit through a bitwise and operation
constexpr bit_value& bit_value::operator&=(
    bit_value other
) noexcept
{
    _value &= other._value;
    return *this;
}

// Assigns the value of the bit through a bitwise or operation
constexpr bit_value& bit_value::operator|=(
    bit_value other
) noexcept
{
    _value |= other._value;
    return *this;
}

// Assigns the value of the bit through a bitwise xor operation
constexpr bit_value& bit_value::operator^=(
    bit_value other
) noexcept
{
    _value ^= other._value;
    return *this;
}
// -------------------------------------------------------------------------- //

// ------------------------- BIT VALUE: CONVERSION -------------------------- //
// Explicitly converts the bit value to a boolean value
constexpr bit_value::operator bool(
) const noexcept
{
    return _value;
}
// -------------------------------------------------------------------------- //

// ------------------------ BIT VALUE: SWAP MEMBERS ------------------------- //
// Swaps the bit value with another bit value
void bit_value::swap(
    bit_value& other
) noexcept
{
    std::swap(*this, other);
}

// Swaps the bit value with the value of a bit reference
template <class T>
void bit_value::swap(
 bit_reference<T> other
) noexcept
{
 if (other != _value) {
 flip();
 other.flip();
 }
}
// -------------------------------------------------------------------------- //

// ---------------------- BIT VALUE: BIT MANIPULATION ----------------------- //
// Sets the value of the bit to the provided boolean value
constexpr bit_value& bit_value::set(
    bool b
) noexcept
{
    _value = b;
    return *this;
}

// Sets the value of the bit to 1
constexpr bit_value& bit_value::set(
) noexcept
{
    _value = true;
    return *this;
}

// Resets the value of the bit to 0
constexpr bit_value& bit_value::reset(
) noexcept
{
    _value = false;
    return *this;
}

// Flips the value of the bit
constexpr bit_value& bit_value::flip(
) noexcept
{
    _value = !_value;
    return *this;
}
// -------------------------------------------------------------------------- //

// ---------------------- BIT VALUE: BITWISE OPERATORS ---------------------- //
// Returns the result of a bitwise not on the right hand side
constexpr bit_value operator~( 
 bit_value rhs
) noexcept
{
 using type = unsigned int;
 return bit_value(static_cast<type>(!rhs._value));
}

// Returns the result of a bitwise and between the left and right hand sides
constexpr bit_value operator&(
 bit_value lhs, 
 bit_value rhs
) noexcept
{
 using type = unsigned int;
 return bit_value(static_cast<type>(lhs._value & rhs._value));
}

// Returns the result of a bitwise or between the left and right hand sides
constexpr bit_value operator|(
 bit_value lhs, 
 bit_value rhs
) noexcept
{
 using type = unsigned int;
 return bit_value(static_cast<type>(lhs._value | rhs._value));
}

// Returns the result of a bitwise xor between the left and right hand sides
constexpr bit_value operator^(
 bit_value lhs, 
 bit_value rhs
) noexcept
{
 using type = unsigned int;
 return bit_value(static_cast<type>(lhs._value ^ rhs._value));
}
// -------------------------------------------------------------------------- //

// -------------------- BIT VALUE: COMPARISON OPERATORS --------------------- //
// Checks if the left hand side is equal to the right hand side
constexpr bool operator==(
    bit_value lhs, 
    bit_value rhs
) noexcept
{
    return lhs._value == rhs._value;
}

// Checks if the left hand side is non equal to the right hand side
constexpr bool operator!=(
    bit_value lhs, 
    bit_value rhs
) noexcept
{
    return lhs._value != rhs._value;
}

// Checks if the left hand side is less than the right hand side
constexpr bool operator<(
 bit_value lhs, 
 bit_value rhs
) noexcept
{
 return lhs._value < rhs._value;
}

// Checks if the left hand side is less than or equal to the right hand side
constexpr bool operator<=(
 bit_value lhs, 
 bit_value rhs
) noexcept
{
 return lhs._value <= rhs._value;
}

// Checks if the left hand side is greater than the right hand side
constexpr bool operator>(
    bit_value lhs, 
    bit_value rhs
) noexcept
{
    return lhs._value > rhs._value;
}

// Checks if the left hand side is greater than or equal to the right hand side
constexpr bool operator>=(
    bit_value lhs, 
    bit_value rhs
) noexcept
{
    return lhs._value >= rhs._value;
}
// -------------------------------------------------------------------------- //

// ---------------------- BIT VALUE: STREAM FUNCTIONS ----------------------- //
// Extracts a bit value from an input stream
template <class CharT, class Traits>
std::basic_istream<CharT, Traits>& operator>>(
 std::basic_istream<CharT, Traits>& is,
 bit_value& x
)
{
 using stream_type = std::basic_istream<CharT, Traits>;
 using traits_type = typename stream_type::traits_type;
 using ios_base = typename stream_type::ios_base;
 constexpr char zero = '0';
 constexpr char one = '1';
 constexpr typename stream_type::int_type eof = traits_type::eof();
 typename ios_base::iostate state = ios_base::goodbit;
 typename stream_type::char_type char_value = 0;
 typename stream_type::int_type int_value = 0;
 typename stream_type::sentry sentry(is);
 bool ok = false;
 bit_value tmp = x;
 if (sentry) {
 try {
 int_value = is.rdbuf()->sbumpc();
 if (traits_type::eq_int_type(int_value, eof)) {
 state |= ios_base::eofbit;
 } else {
 char_value = traits_type::to_char_type(int_value);
 if (traits_type::eq(char_value, is.widen(zero))) {
 tmp.reset();
 ok = true;
 } else if (traits_type::eq(char_value, is.widen(one))) {
 tmp.set();
 ok = true;
 } else {
 int_value = is.rdbuf()->sputbackc(char_value);
 if (traits_type::eq_int_type(int_value, eof)) {
 state |= ios_base::failbit;
 }
 }
 }
 } catch(...) {
 is.setstate(ios_base::badbit);
 }
 }
 if (ok) {
 x = tmp;
 } else {
 state |= ios_base::failbit;
 }
 state ? is.setstate(state) : void();
 return is;
}

// Inserts a bit value in an output stream
template <class CharT, class Traits>
std::basic_ostream<CharT, Traits>& operator<<(
 std::basic_ostream<CharT, Traits>& os,
 bit_value x
)
{
 constexpr char zero = '0';
 constexpr char one = '1';
 return os << os.widen(x ? one : zero);
}
// -------------------------------------------------------------------------- //

// -------------------------- BIT VALUE: CONSTANTS -------------------------- //
// Constant bit values
constexpr bit_value bit_off(0U);
constexpr bit_value bit_on(1U);
constexpr bit_value bit0(0U);
constexpr bit_value bit1(1U);
// -------------------------------------------------------------------------- //

// ========================================================================== //
} // namespace bit
#endif // _BIT_VALUE_HPP_INCLUDED
// ========================================================================== //

// ============================= BIT REFERENCE ============================== //
// Project:         The C++ Bit Library
// Name:            bit_reference.hpp
// Description:     A class representing a reference to a bit
// Creator:         Vincent Reverdy
// Contributor(s):  Vincent Reverdy [2015-2017]
// License:         BSD 3-Clause License
// ========================================================================== //
#ifndef _BIT_REFERENCE_HPP_INCLUDED
#define _BIT_REFERENCE_HPP_INCLUDED
// ========================================================================== //

/* ***************************** BIT REFERENCE ****************************** */
// Bit reference class definition
template <class WordType>
class bit_reference
{
 // Assertions
 static_assert(binary_digits<WordType>::value, "");

// Friendship
 template <class> friend class bit_reference;
 friend class bit_pointer<WordType>;
 
 // Types
 public:
 using word_type = WordType;
 using size_type = std::size_t;

// Lifecycle
 public:
 template <class T> 
 constexpr bit_reference(const bit_reference<T>& other) noexcept;
 explicit constexpr bit_reference(word_type& ref) noexcept;
 constexpr bit_reference(word_type& ref, size_type pos);

// Assignment
 public:
 constexpr bit_reference& operator=(const bit_reference& other) noexcept;
 template <class T> 
 constexpr bit_reference& operator=(const bit_reference<T>& other) noexcept;
 constexpr bit_reference& operator=(bit_value val) noexcept;
 constexpr bit_reference& assign(word_type val) noexcept;
 constexpr bit_reference& assign(word_type val, size_type pos);

// Bitwise assignment operators
    public:
    constexpr bit_reference& operator&=(bit_value other) noexcept;
    constexpr bit_reference& operator|=(bit_value other) noexcept;
    constexpr bit_reference& operator^=(bit_value other) noexcept;
    
    // Conversion
    public:
    explicit constexpr operator bool() const noexcept;

// Access
 public:
 constexpr bit_pointer<WordType> operator&() const noexcept;
 
 // Swap members
 public:
 template <class T> 
 void swap(bit_reference<T> other);
 void swap(bit_value& other);

// Bit manipulation
    public:
    constexpr bit_reference& set(bool b) noexcept;
    constexpr bit_reference& set() noexcept;
    constexpr bit_reference& reset() noexcept;
    constexpr bit_reference& flip() noexcept;

// Underlying details
 public:
 constexpr word_type* address() const noexcept;
 constexpr size_type position() const noexcept;
 constexpr typename std::remove_cv<word_type>::type mask() const noexcept;

// Implementation details: function members
    private:
    bit_reference() noexcept = default;
    explicit constexpr bit_reference(std::nullptr_t) noexcept;
    explicit constexpr bit_reference(word_type* ptr) noexcept;
    constexpr bit_reference(word_type* ptr, size_type pos);

// Implementation details: data members
 private:
 word_type* _ptr;
 typename std::remove_cv<word_type>::type _mask;
};

// Swap
template <class T, class U>
void swap(
 bit_reference<T> lhs,
 bit_reference rhs
) noexcept;
template <class T>
void swap(
 bit_reference<T> lhs,
 bit_value& rhs
) noexcept;
template <class U>
void swap(
 bit_value& lhs,
 bit_reference rhs
) noexcept;

// Stream functions
template <class CharT, class Traits, class T>
std::basic_istream<CharT, Traits>& operator>>(
 std::basic_istream<CharT, Traits>& is,
 bit_reference<T>& x
);
template <class CharT, class Traits, class T>
std::basic_ostream<CharT, Traits>& operator<<(
 std::basic_ostream<CharT, Traits>& os,
 bit_reference<T> x
);
/* ************************************************************************** */

// ------------------------ BIT REFERENCE: LIFECYCLE ------------------------ //
// Implicitly constructs a bit reference from another bit reference
template <class WordType>
template <class T> 
constexpr bit_reference<WordType>::bit_reference(
 const bit_reference<T>& other
) noexcept
: _ptr(other._ptr)
, _mask(other._mask)
{
}

// Explicitly constructs an aligned bit reference
template <class WordType>
constexpr bit_reference<WordType>::bit_reference(
 word_type& ref
) noexcept
: _ptr(&ref)
, _mask(1)
{
}

// Explicitly constructs an unaligned bit reference
template <class WordType>
constexpr bit_reference<WordType>::bit_reference(
 word_type& ref, 
 size_type pos
)
: _ptr((assert(pos < binary_digits<word_type>::value), &ref))
, _mask(static_cast<word_type>(1) << pos)
{
}
// -------------------------------------------------------------------------- //

// ----------------------- BIT REFERENCE: ASSIGNMENT ------------------------ //
// Copies a bit reference to the bit reference
template <class WordType>
constexpr bit_reference<WordType>& bit_reference<WordType>::operator=(
 const bit_reference& other
) noexcept
{
 other ? set() : reset();
 return *this;
}

// Assigns a bit reference to the bit reference
template <class WordType>
template <class T> 
constexpr bit_reference<WordType>& bit_reference<WordType>::operator=(
 const bit_reference<T>& other
) noexcept
{
 other ? set() : reset();
 return *this;
}

// Assigns a bit value to the bit reference
template <class WordType>
constexpr bit_reference<WordType>& bit_reference<WordType>::operator=(
 bit_value val
) noexcept
{
 val ? set() : reset();
 return *this;
}

// Assigns the aligned bit of a value to the bit reference
template <class WordType>
constexpr bit_reference<WordType>& bit_reference<WordType>::assign(
 word_type val
) noexcept
{
 val & 1 ? set() : reset();
 return *this;
}

// Assigns an unaligned bit of a value to the bit reference
template <class WordType>
constexpr bit_reference<WordType>& bit_reference<WordType>::assign(
 word_type val, 
 size_type pos
)
{
 assert(pos < binary_digits<word_type>::value);
 val >> pos & 1 ? set() : reset();
 return *this;
}
// -------------------------------------------------------------------------- //

// -------------- BIT REFERENCE: BITWISE ASSIGNMENT OPERATORS --------------- //
// Assigns the value of the referenced bit through a bitwise and operation
template <class WordType>
constexpr bit_reference<WordType>& bit_reference<WordType>::operator&=(
 bit_value other
) noexcept
{
 *_ptr &= ~(_mask * static_cast<word_type>(!other._value));
 return *this;
}

// Assigns the value of the referenced bit through a bitwise or operation
template <class WordType>
constexpr bit_reference<WordType>& bit_reference<WordType>::operator|=(
 bit_value other
) noexcept
{
 *_ptr |= _mask * static_cast<word_type>(other._value);
 return *this;
}

// Assigns the value of the referenced bit through a bitwise xor operation
template <class WordType>
constexpr bit_reference<WordType>& bit_reference<WordType>::operator^=(
 bit_value other
) noexcept
{
 *_ptr ^= _mask * static_cast<word_type>(other._value);
 return *this;
}
// -------------------------------------------------------------------------- //

// ----------------------- BIT REFERENCE: CONVERSION ------------------------ //
// Explicitly converts the bit reference to a boolean value
template <class WordType>
constexpr bit_reference<WordType>::operator bool(
) const noexcept
{
 return *_ptr & _mask;
}
// -------------------------------------------------------------------------- //

// ------------------------- BIT REFERENCE: ACCESS -------------------------- //
// Gets a bit pointer from the bit reference
template <class WordType>
constexpr bit_pointer<WordType> bit_reference<WordType>::operator&(
) const noexcept
{
 return bit_pointer<WordType>(_ptr, position());
}
// -------------------------------------------------------------------------- //

// ---------------------- BIT REFERENCE: SWAP MEMBERS ----------------------- //
// Swaps the value of the referenced bit with another bit reference
template <class WordType>
template <class T>
void bit_reference<WordType>::swap(
 bit_reference<T> other
)
{
 if (other != *this) {
 flip();
 other.flip();
 }
}

// Swaps the value of the referenced bit with a bit value
template <class WordType>
void bit_reference<WordType>::swap(
 bit_value& other
)
{
 if (other != *this) {
 flip();
 other.flip();
 }
}
// -------------------------------------------------------------------------- //

// -------------------- BIT REFERENCE: BIT MANIPULATION --------------------- //
// Sets the value of the referenced bit to the provided boolean value
template <class WordType>
constexpr bit_reference<WordType>& bit_reference<WordType>::set(
 bool b
) noexcept
{
 b ? set() : reset();
 return *this;
}

// Sets the value of the referenced bit to 1
template <class WordType>
constexpr bit_reference<WordType>& bit_reference<WordType>::set(
) noexcept
{
 *_ptr |= _mask;
 return *this;
}

// Resets the value of the referenced bit to 0
template <class WordType>
constexpr bit_reference<WordType>& bit_reference<WordType>::reset(
) noexcept
{
 *_ptr &= ~_mask;
 return *this;
}

// Flips the value of the referenced bit
template <class WordType>
constexpr bit_reference<WordType>& bit_reference<WordType>::flip(
) noexcept
{
 *_ptr ^= _mask;
 return *this;
}
// -------------------------------------------------------------------------- //

// ------------------- BIT REFERENCE: UNDERLYING DETAILS -------------------- //
// Returns a pointer to the underlying word
template <class WordType>
constexpr typename bit_reference<WordType>::word_type* 
bit_reference<WordType>::address(
) const noexcept
{
 return _ptr;
}

// Returns the position of the referenced bit within the underlying word
template <class WordType>
constexpr typename bit_reference<WordType>::size_type
bit_reference<WordType>::position(
) const noexcept
{
 return _tzcnt(_mask);
}

// Returns a mask corresponding to the referenced bit
template <class WordType>
constexpr typename std::remove_cv<
 typename bit_reference<WordType>::word_type
>::type bit_reference<WordType>::mask(
) const noexcept
{
 return _mask;
}
// -------------------------------------------------------------------------- //

// -------------------------- BIT REFERENCE: SWAP --------------------------- //
// Swaps two bit references
template <class T, class U>
void swap(
 bit_reference<T> lhs,
 bit_reference rhs
) noexcept
{
 if (lhs != rhs) {
 lhs.flip();
 rhs.flip();
 }
}

// Swaps a bit reference and a bit value
template <class T>
void swap(
 bit_reference<T> lhs,
 bit_value& rhs
) noexcept
{
 if (lhs != rhs) {
 lhs.flip();
 rhs.flip();
 }
}

// Swaps a bit value and a bit reference
template <class U>
void swap(
 bit_value& lhs,
 bit_reference rhs
) noexcept
{
 if (lhs != rhs) {
 lhs.flip();
 rhs.flip();
 }
}
// -------------------------------------------------------------------------- //

// -------------------- BIT REFERENCE: STREAM FUNCTIONS --------------------- //
// Extracts a bit reference from an input stream
template <class CharT, class Traits, class T>
std::basic_istream<CharT, Traits>& operator>>(
 std::basic_istream<CharT, Traits>& is,
 bit_reference<T>& x
)
{
 using stream_type = std::basic_istream<CharT, Traits>;
 using traits_type = typename stream_type::traits_type;
 using ios_base = typename stream_type::ios_base;
 constexpr char zero = '0';
 constexpr char one = '1';
 constexpr typename stream_type::int_type eof = traits_type::eof();
 typename ios_base::iostate state = ios_base::goodbit;
 typename stream_type::char_type char_value = 0;
 typename stream_type::int_type int_value = 0;
 typename stream_type::sentry sentry(is);
 bool ok = false;
 bit_value tmp = x;
 if (sentry) {
 try {
 int_value = is.rdbuf()->sbumpc();
 if (traits_type::eq_int_type(int_value, eof)) {
 state |= ios_base::eofbit;
 } else {
 char_value = traits_type::to_char_type(int_value);
 if (traits_type::eq(char_value, is.widen(zero))) {
 tmp.reset();
 ok = true;
 } else if (traits_type::eq(char_value, is.widen(one))) {
 tmp.set();
 ok = true;
 } else {
 int_value = is.rdbuf()->sputbackc(char_value);
 if (traits_type::eq_int_type(int_value, eof)) {
 state |= ios_base::failbit;
 }
 }
 }
 } catch(...) {
 is.setstate(ios_base::badbit);
 }
 }
 if (ok) {
 x = tmp;
 } else {
 state |= ios_base::failbit;
 }
 state ? is.setstate(state) : void();
 return is;
}

// Inserts a bit reference in an output stream
template <class CharT, class Traits, class T>
std::basic_ostream<CharT, Traits>& operator<<(
 std::basic_ostream<CharT, Traits>& os,
 bit_reference<T> x
)
{
 constexpr char zero = '0';
 constexpr char one = '1';
 return os << os.widen(x ? one : zero);
}
// -------------------------------------------------------------------------- //

// -------- BIT REFERENCE: IMPLEMENTATION DETAILS: FUNCTION MEMBERS --------- //
// Privately explicitly constructs a bit reference from a nullptr
template <class WordType>
constexpr bit_reference<WordType>::bit_reference(
 std::nullptr_t
) noexcept
: _ptr(nullptr)
, _mask()
{
}
 
// Privately explicitly constructs an aligned bit reference from a pointer
template <class WordType>
constexpr bit_reference<WordType>::bit_reference(
 word_type* ptr
) noexcept
: _ptr(ptr)
, _mask(1)
{
}

// Privately explicitly constructs an unaligned bit reference from a pointer
template <class WordType>
constexpr bit_reference<WordType>::bit_reference(
 word_type* ptr, 
 size_type pos
)
: _ptr((assert(pos < binary_digits<word_type>::value), ptr))
, _mask(static_cast<word_type>(1) << pos)
{
}
// -------------------------------------------------------------------------- //

// ========================================================================== //
} // namespace bit
#endif // _BIT_REFERENCE_HPP_INCLUDED
// ========================================================================== //

// ============================== BIT ITERATOR ============================== //
// Project:         The C++ Bit Library
// Name:            bit_iterator.hpp
// Description:     A class representing an iterator on bit sequences
// Creator:         Vincent Reverdy
// Contributor(s):  Vincent Reverdy [2015-2017]
// License:         BSD 3-Clause License
// ========================================================================== //
#ifndef _BIT_ITERATOR_HPP_INCLUDED
#define _BIT_ITERATOR_HPP_INCLUDED
// ========================================================================== //

/* ****************************** BIT ITERATOR ****************************** */
// Bit iterator class definition
template <class Iterator>
class bit_iterator
{
 // Assertions
 private:
 using _traits_t = _cv_iterator_traits<Iterator>;
 static_assert(binary_digits<typename _traits_t::value_type>::value, "");
 
 // Types
 public:
 using iterator_type = Iterator;
 using word_type = typename _traits_t::value_type;
 using iterator_category = typename _traits_t::iterator_category;
 using value_type = bit_value;
 using difference_type = std::ptrdiff_t;
 using pointer = bit_pointer<word_type>;
 using reference = bit_reference<word_type>;
 using size_type = std::size_t;

// Lifecycle
 public:
 constexpr bit_iterator();
 template <class T> 
 constexpr bit_iterator(const bit_iterator<T>& other);
 explicit constexpr bit_iterator(iterator_type i);
 constexpr bit_iterator(iterator_type i, size_type pos);

// Assignment
 public:
 template <class T>
 constexpr bit_iterator& operator=(const bit_iterator<T>& other);

// Access
    public:
    constexpr reference operator*() const noexcept;
    constexpr pointer operator->() const noexcept;
    constexpr reference operator[](difference_type n) const;

// Increment and decrement operators
    public:
    constexpr bit_iterator& operator++();
    constexpr bit_iterator& operator--();
    constexpr bit_iterator operator++(int);
    constexpr bit_iterator operator--(int);
    constexpr bit_iterator operator+(difference_type n) const;
    constexpr bit_iterator operator-(difference_type n) const;
    constexpr bit_iterator& operator+=(difference_type n);
    constexpr bit_iterator& operator-=(difference_type n);

// Underlying details
 public:
 constexpr iterator_type base() const;
 constexpr size_type position() const noexcept;
 constexpr typename std::remove_cv<word_type>::type mask() const noexcept;

// Implementation details: data members
    private:
    iterator_type _current;
    size_type _position;

// Non-member arithmetic operators
 template <class T>
 friend constexpr bit_iterator<T> operator+(
 typename bit_iterator<T>::difference_type n,
 const bit_iterator<T>& i
 );
 template <class T, class U>
 friend constexpr typename std::common_type<
 typename bit_iterator<T>::difference_type,
 typename bit_iterator::difference_type
 >::type operator-(
 const bit_iterator<T>& lhs,
 const bit_iterator& rhs
 );

// Comparison operators
 public:
 template <class T, class U>
 friend constexpr bool operator==(
 const bit_iterator<T>& lhs, 
 const bit_iterator& rhs
 );
 template <class T, class U>
 friend constexpr bool operator!=(
 const bit_iterator<T>& lhs, 
 const bit_iterator& rhs
 );
 template <class T, class U>
 friend constexpr bool operator<(
 const bit_iterator<T>& lhs, 
 const bit_iterator& rhs
 );
 template <class T, class U>
 friend constexpr bool operator<=(
 const bit_iterator<T>& lhs, 
 const bit_iterator& rhs
 );
 template <class T, class U>
 friend constexpr bool operator>(
 const bit_iterator<T>& lhs, 
 const bit_iterator& rhs
 );
 template <class T, class U>
 friend constexpr bool operator>=(
 const bit_iterator<T>& lhs, 
 const bit_iterator& rhs
 );
};
/* ************************************************************************** */

// ------------------------ BIT ITERATOR: LIFECYCLE ------------------------- //
// Implicitly default constructs a bit iterator
template <class Iterator>
constexpr bit_iterator<Iterator>::bit_iterator(
)
: _current()
, _position()
{
}

// Implicitly constructs a bit iterator from another bit iterator
template <class Iterator>
template <class T> 
constexpr bit_iterator<Iterator>::bit_iterator(
 const bit_iterator<T>& other
)
: _current(other._current)
, _position(other._position)
{
}

// Explicitly constructs an aligned bit iterator from an iterator
template <class Iterator>
constexpr bit_iterator<Iterator>::bit_iterator(
 iterator_type i
)
: _current(i)
, _position(0)
{
}

// Explicitly constructs an unaligned bit iterator from an iterator
template <class Iterator>
constexpr bit_iterator<Iterator>::bit_iterator(
 iterator_type i, 
 size_type pos
)
: _current(i)
, _position((assert(pos < binary_digits<word_type>::value), pos))
{
}
// -------------------------------------------------------------------------- //

// ------------------------ BIT ITERATOR: ASSIGNMENT ------------------------ //
// Assigns a bit iterator to the bit iterator
template <class Iterator>
template <class T> 
constexpr bit_iterator<Iterator>& bit_iterator<Iterator>::operator=(
 const bit_iterator<T>& other
)
{
 _current = other._current;
 _position = other._position;
 return *this;
}
// -------------------------------------------------------------------------- //

// -------------------------- BIT ITERATOR: ACCESS -------------------------- //
// Gets a bit reference from the bit iterator
template <class Iterator>
constexpr typename bit_iterator<Iterator>::reference 
bit_iterator<Iterator>::operator*(
) const noexcept
{
 return reference(*_current, _position);
}

// Gets a pointer to a bit
template <class Iterator>
constexpr typename bit_iterator<Iterator>::pointer 
bit_iterator<Iterator>::operator->(
) const noexcept
{
 return pointer(&*_current, _position);
}

// Gets a bit reference, decrementing or incrementing the iterator
template <class Iterator>
constexpr typename bit_iterator<Iterator>::reference 
bit_iterator<Iterator>::operator[](
 difference_type n
) const
{
 constexpr difference_type digits = binary_digits<word_type>::value;
 const difference_type sum = _position + n;
 difference_type diff = sum / digits;
 if (sum < 0 && diff * digits != sum) {
 --diff;
 }
 return reference(*std::next(_current, diff), sum - diff * digits);
}
// -------------------------------------------------------------------------- //

// ------------- BIT ITERATOR: INCREMENT AND DECREMENT OPERATORS ------------ //
// Increments the bit iterator and returns it
template <class Iterator>
constexpr bit_iterator<Iterator>& bit_iterator<Iterator>::operator++(
)
{
 constexpr size_type digits = binary_digits<word_type>::value;
 if (_position + 1 < digits) {
 ++_position;
 } else {
 ++_current;
 _position = 0;
 }
 return *this;
}

// Decrements the bit iterator and returns it
template <class Iterator>
constexpr bit_iterator<Iterator>& bit_iterator<Iterator>::operator--(
)
{
 constexpr size_type digits = binary_digits<word_type>::value;
 if (_position) {
 --_position;
 } else {
 --_current;
 _position = digits - 1;
 }
 return *this;
}

// Increments the bit iterator and returns the old one
template <class Iterator>
constexpr bit_iterator<Iterator> bit_iterator<Iterator>::operator++(
 int
)
{
 bit_iterator old = *this;
 ++(*this);
 return old;
}

// Decrements the bit iterator and returns the old one
template <class Iterator>
constexpr bit_iterator<Iterator> bit_iterator<Iterator>::operator--(
 int
)
{
 bit_iterator old = *this;
 --(*this);
 return old;
}

// Looks forward several bits and gets an iterator at this position
template <class Iterator>
constexpr bit_iterator<Iterator> bit_iterator<Iterator>::operator+(
 difference_type n
) const
{
 constexpr difference_type digits = binary_digits<word_type>::value;
 const difference_type sum = _position + n;
 difference_type diff = sum / digits;
 if (sum < 0 && diff * digits != sum) {
 --diff;
 }
 return bit_iterator(std::next(_current, diff), sum - diff * digits);
}

// Looks backward several bits and gets an iterator at this position
template <class Iterator>
constexpr bit_iterator<Iterator> bit_iterator<Iterator>::operator-(
 difference_type n
) const
{
 constexpr difference_type digits = binary_digits<word_type>::value;
 const difference_type sum = _position - n;
 difference_type diff = sum / digits;
 if (sum < 0 && diff * digits != sum) {
 --diff;
 }
 return bit_iterator(std::next(_current, diff), sum - diff * digits);
}

// Increments the iterator by several bits and returns it
template <class Iterator>
constexpr bit_iterator<Iterator>& bit_iterator<Iterator>::operator+=(
 difference_type n
)
{
 *this = *this + n;
 return *this;
}

// Decrements the iterator by several bits and returns it
template <class Iterator>
constexpr bit_iterator<Iterator>& bit_iterator<Iterator>::operator-=(
 difference_type n
)
{
 *this = *this - n;
 return *this;
}
// -------------------------------------------------------------------------- //

// -------------------- BIT ITERATOR: UNDERLYING DETAILS -------------------- //
// Returns a copy of the underlying iterator
template <class Iterator>
constexpr typename bit_iterator<Iterator>::iterator_type 
bit_iterator<Iterator>::base(
) const
{
 return _current;
}

// Returns the position of the bit within the underlying word
template <class Iterator>
constexpr typename bit_iterator<Iterator>::size_type
bit_iterator<Iterator>::position(
) const noexcept
{
 return _position;
}

// Returns a mask corresponding to the bit associated with the iterator
template <class Iterator>
constexpr typename std::remove_cv<
 typename bit_iterator<Iterator>::word_type 
>::type bit_iterator<Iterator>::mask(
) const noexcept
{
 return static_cast<word_type>(1) << _position;
}
// -------------------------------------------------------------------------- //

// -------------- BIT ITERATOR: NON-MEMBER ARITHMETIC OPERATORS ------------- //
// Advances the bit iterator several times
template <class T>
constexpr bit_iterator<T> operator+(
 typename bit_iterator<T>::difference_type n,
 const bit_iterator<T>& i
)
{
 return i + n;
}

// Computes the distance in bits separating two bit iterators
template <class T, class U>
constexpr typename std::common_type<
 typename bit_iterator<T>::difference_type,
 typename bit_iterator::difference_type
>::type operator-(
 const bit_iterator<T>& lhs,
 const bit_iterator& rhs
)
{
 using lhs_utype = typename bit_iterator<T>::word_type;
 using rhs_utype = typename bit_iterator::word_type;
 using lhs_type = typename bit_iterator<T>::difference_type;
 using rhs_type = typename bit_iterator::difference_type;
 using difference_type = typename std::common_type<lhs_type, rhs_type>::type;
 constexpr difference_type lhs_digits = binary_digits<lhs_utype>::value;
 constexpr difference_type rhs_digits = binary_digits<rhs_utype>::value;
 constexpr difference_type digits = rhs_digits;
 static_assert(lhs_digits == rhs_digits, "");
 const difference_type main = lhs._current - rhs._current;
 return main * digits + (lhs._position - rhs._position);
}
// -------------------------------------------------------------------------- //

// ------------------- BIT ITERATOR: COMPARISON OPERATORS ------------------- //
// Checks if the left hand side is equal to the right hand side
template <class T, class U>
constexpr bool operator==(
 const bit_iterator<T>& lhs, 
 const bit_iterator& rhs
)
{
 return lhs._current == rhs._current && lhs._position == rhs._position;
}

// Checks if the left hand side is non equal to the right hand side
template <class T, class U>
constexpr bool operator!=(
 const bit_iterator<T>& lhs, 
 const bit_iterator& rhs
)
{
 return lhs._current != rhs._current || lhs._position != rhs._position;
}

// Checks if the left hand side is less than the right hand side
template <class T, class U>
constexpr bool operator<(
 const bit_iterator<T>& lhs, 
 const bit_iterator& rhs
)
{
 return lhs._current < rhs._current 
 || (lhs._current == rhs._current && lhs._position < rhs._position);
}

// Checks if the left hand side is less than or equal to the right hand side
template <class T, class U>
constexpr bool operator<=(
 const bit_iterator<T>& lhs, 
 const bit_iterator& rhs
)
{
 return lhs._current < rhs._current 
 || (lhs._current == rhs._current && lhs._position <= rhs._position);
}

// Checks if the left hand side is greater than the right hand side
template <class T, class U>
constexpr bool operator>(
 const bit_iterator<T>& lhs, 
 const bit_iterator& rhs
)
{
 return lhs._current > rhs._current 
 || (lhs._current == rhs._current && lhs._position > rhs._position);
}

// Checks if the left hand side is greater than or equal to the right hand side
template <class T, class U>
constexpr bool operator>=(
 const bit_iterator<T>& lhs, 
 const bit_iterator& rhs
)
{
 return lhs._current > rhs._current 
 || (lhs._current == rhs._current && lhs._position >= rhs._position);
}
// -------------------------------------------------------------------------- //

// ========================================================================== //
} // namespace bit
#endif // _BIT_ITERATOR_HPP_INCLUDED
// ========================================================================== //

namespace my {
    using bit::bit_iterator;
    using bit::binary_digits_v;
}

using uint = unsigned int;

template<class FwdIt, class FwdIt2>
inline FwdIt2 naive_xor_copy(FwdIt first, FwdIt last, FwdIt2 d_first)
{
 while (first != last) {
 *d_first ^= *first;
 ++d_first;
 ++first;
 }
 return d_first;
}

uint naive_foo(const uint i1, uint i2)
{
 auto source_begin = my::bit_iterator<const uint*>(&i1, 3);
 auto source_end = my::bit_iterator<const uint*>(&i1, 9);
 auto dest_begin = my::bit_iterator<uint*>(&i2);
 naive_xor_copy(source_begin, source_end, dest_begin);
 return i2;
}

template<class WT>
inline constexpr WT mask(size_t lo_pos, size_t size) {
 constexpr size_t N = my::binary_digits_v<WT>;
 if (lo_pos == 0 && size == N) {
 return WT(-1);
 } else {
 WT mask = (WT(1) << size) - WT(1);
 return mask << lo_pos;
 }
}

template<class WT1, class WT2, class = std::enable_if_t<my::binary_digits_v<WT1> == my::binary_digits_v<WT2>>>
inline my::bit_iterator<WT2*> __attribute__((always_inline)) advanced_xor_copy(my::bit_iterator<WT1*> first, my::bit_iterator<WT1*> last, my::bit_iterator<WT2*> d_first)
{
 if (first.base() == last.base()) {
 size_t size = (last - first);
 if (d_first.position() + size <= my::binary_digits_v<WT2>) {
 auto& dest = *d_first.base();
 auto& src = *first.base();
 WT1 src_bits = ((src >> first.position()) & mask<WT1>(0, size));
 WT2 dst_bits = WT2(src_bits) << d_first.position();
 dest = (dest & ~mask<WT2>(d_first.position(), size)) | dst_bits;
 d_first += size;
 return d_first;
 }
 }
 return naive_xor_copy(first, last, d_first);
}

uint advanced_foo(const uint i1, uint i2)
{
 auto source_begin = my::bit_iterator<const uint*>(&i1, 3);
 auto source_end = my::bit_iterator<const uint*>(&i1, 9);
 auto dest_begin = my::bit_iterator<uint*>(&i2);
 advanced_xor_copy(source_begin, source_end, dest_begin);
 return i2;
}

uint perfect_foo(const uint i1, uint i2)
{
    return (i2 & ~0x003F) | ((i1 >> 3) & 0x003F);
}

uint perfect2_foo(const uint i1, uint i2)
{
    return i2 ^ (0x003F & (i2 ^ (i1 >> 3)));
}