/bitcoin/src/util/bitset.h

Source
// Copyright (c) The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.

#ifndef BITCOIN_UTIL_BITSET_H
#define BITCOIN_UTIL_BITSET_H

#include <util/check.h>
#include <util/overflow.h>

#include <array>
#include <bit>
#include <cstdint>
#include <limits>
#include <type_traits>

/* This file provides data types similar to std::bitset, but adds the following functionality:
 *
 * - Efficient iteration over all set bits (compatible with range-based for loops).
 * - Efficient search for the first and last set bit (First() and Last()).
 * - Efficient set subtraction: (a - b) implements "a and not b".
 * - Efficient non-strict subset/superset testing: IsSubsetOf() and IsSupersetOf().
 * - Efficient set overlap testing: a.Overlaps(b)
 * - Efficient construction of set containing 0..N-1 (S::Fill).
 * - Efficient construction of a single set (S::Singleton).
 * - Construction from initializer lists.
 *
 * Other differences:
 * - BitSet<N> is a bitset that supports at least N elements, but may support more (Size() reports
 *   the actual number). Because the actual number is unpredictable, there are no operations that
 *   affect all positions (like std::bitset's operator~, flip(), or all()).
 * - Various other unimplemented features.
 */

namespace bitset_detail {

/** Count the number of bits set in an unsigned integer type. */
template<typename I>
unsigned inline constexpr PopCount(I v)
{
    static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
    constexpr auto BITS = std::numeric_limits<I>::digits;
    // Algorithms from https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation.
    // These seem to be faster than std::popcount when compiling for non-SSE4 on x86_64.
    if constexpr (BITS <= 32) {
        v -= (v >> 1) & 0x55555555;
        v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
        v = (v + (v >> 4)) & 0x0f0f0f0f;
        if constexpr (BITS > 8) v += v >> 8;
        if constexpr (BITS > 16) v += v >> 16;
        return v & 0x3f;
    } else {
        static_assert(BITS <= 64);
        v -= (v >> 1) & 0x5555555555555555;
        v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333);
        v = (v + (v >> 4)) & 0x0f0f0f0f0f0f0f0f;
        return (v * uint64_t{0x0101010101010101}) >> 56;
    }
}

/** A bitset implementation backed by a single integer of type I. */
template<typename I>
class IntBitSet
{
    // Only binary, unsigned, integer, types allowed.
    static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
    /** The maximum number of bits this bitset supports. */
    static constexpr unsigned MAX_SIZE = std::numeric_limits<I>::digits;
    /** Integer whose bits represent this bitset. */
    I m_val;
    /** Internal constructor with a given integer as contents. */
    IntBitSet(I val) noexcept : m_val{val} {}
    /** Dummy type to return using end(). Only used for comparing with Iterator. */
    class IteratorEnd
    {
        friend class IntBitSet;
        constexpr IteratorEnd() = default;
    public:
        constexpr IteratorEnd(const IteratorEnd&) = default;
    };
    /** Iterator type returned by begin(), which efficiently iterates all 1 positions. */
    class Iterator
    {
        friend class IntBitSet;
        I m_val; /**< The original integer's remaining bits. */
        unsigned m_pos; /** Last reported 1 position (if m_pos != 0). */
        constexpr Iterator(I val) noexcept : m_val(val), m_pos(0)
        {
            if (m_val != 0) m_pos = std::countr_zero(m_val);
        }
    public:
        /** Do not allow external code to construct an Iterator. */
        Iterator() = delete;
        // Copying is allowed.
        constexpr Iterator(const Iterator&) noexcept = default;
        constexpr Iterator& operator=(const Iterator&) noexcept = default;
        /** Test whether we are done (can only compare with IteratorEnd). */
        constexpr friend bool operator==(const Iterator& a, const IteratorEnd&) noexcept
        {
            return a.m_val == 0;
        }
        /** Progress to the next 1 bit (only if != IteratorEnd). */
        constexpr Iterator& operator++() noexcept
        {
            Assume(m_val != 0);
            m_val &= m_val - I{1U};
            if (m_val != 0) m_pos = std::countr_zero(m_val);
            return *this;
        }
        /** Get the current bit position (only if != IteratorEnd). */
        constexpr unsigned operator*() const noexcept
        {
            Assume(m_val != 0);
            return m_pos;
        }
    };

public:
    /** Construct an all-zero bitset. */
    constexpr IntBitSet() noexcept : m_val{0} {}
    /** Copy construct a bitset. */
    constexpr IntBitSet(const IntBitSet&) noexcept = default;
    /** Construct from a list of values. */
    constexpr IntBitSet(std::initializer_list<unsigned> ilist) noexcept : m_val(0)
    {
        for (auto pos : ilist) Set(pos);
    }
    /** Copy assign a bitset. */
    constexpr IntBitSet& operator=(const IntBitSet&) noexcept = default;
    /** Assign from a list of positions (which will be made true, all others false). */
    constexpr IntBitSet& operator=(std::initializer_list<unsigned> ilist) noexcept
    {
        m_val = 0;
        for (auto pos : ilist) Set(pos);
        return *this;
    }
    /** Construct a bitset with the singleton i. */
    static constexpr IntBitSet Singleton(unsigned i) noexcept
    {
        Assume(i < MAX_SIZE);
        return IntBitSet(I(1U) << i);
    }
    /** Construct a bitset with bits 0..count-1 (inclusive) set to 1. */
    static constexpr IntBitSet Fill(unsigned count) noexcept
    {
        IntBitSet ret;
        Assume(count <= MAX_SIZE);
        if (count) ret.m_val = I(~I{0}) >> (MAX_SIZE - count);
        return ret;
    }
    /** Set a bit to 1. */
    constexpr void Set(unsigned pos) noexcept
    {
        Assume(pos < MAX_SIZE);
        m_val |= I{1U} << pos;
    }
    /** Set a bit to the specified value. */
    constexpr void Set(unsigned pos, bool val) noexcept
    {
        Assume(pos < MAX_SIZE);
        m_val = (m_val & ~I(I{1U} << pos)) | (I(val) << pos);
    }
    /** Set a bit to 0. */
    constexpr void Reset(unsigned pos) noexcept
    {
        Assume(pos < MAX_SIZE);
        m_val &= ~I(I{1U} << pos);
    }
    /** Retrieve a bit at the given position. */
    constexpr bool operator[](unsigned pos) const noexcept
    {
        Assume(pos < MAX_SIZE);
        return (m_val >> pos) & 1U;
    }
    /** Compute the number of 1 bits in the bitset. */
    constexpr unsigned Count() const noexcept { return PopCount(m_val); }
    /** Return the number of bits that this object holds. */
    static constexpr unsigned Size() noexcept { return MAX_SIZE; }
    /** Check if all bits are 0. */
    constexpr bool None() const noexcept { return m_val == 0; }
    /** Check if any bits are 1. */
    constexpr bool Any() const noexcept { return !None(); }
    /** Return an object that iterates over all 1 bits (++ and * only allowed when != end()). */
    constexpr Iterator begin() const noexcept { return Iterator(m_val); }
    /** Return a dummy object to compare Iterators with. */
    constexpr IteratorEnd end() const noexcept { return IteratorEnd(); }
    /** Find the first element (requires Any()). */
    constexpr unsigned First() const noexcept
    {
        Assume(m_val != 0);
        return std::countr_zero(m_val);
    }
    /** Find the last element (requires Any()). */
    constexpr unsigned Last() const noexcept
    {
        Assume(m_val != 0);
        return std::bit_width(m_val) - 1;
    }
    /** Set this object's bits to be the binary AND between respective bits from this and a. */
    constexpr IntBitSet& operator|=(const IntBitSet& a) noexcept { m_val |= a.m_val; return *this; }
    /** Set this object's bits to be the binary OR between respective bits from this and a. */
    constexpr IntBitSet& operator&=(const IntBitSet& a) noexcept { m_val &= a.m_val; return *this; }
    /** Set this object's bits to be the binary AND NOT between respective bits from this and a. */
    constexpr IntBitSet& operator-=(const IntBitSet& a) noexcept { m_val &= ~a.m_val; return *this; }
    /** Set this object's bits to be the binary XOR between respective bits from this as a. */
    constexpr IntBitSet& operator^=(const IntBitSet& a) noexcept { m_val ^= a.m_val; return *this; }
    /** Check if the intersection between two sets is non-empty. */
    constexpr bool Overlaps(const IntBitSet& a) const noexcept { return m_val & a.m_val; }
    /** Return an object with the binary AND between respective bits from a and b. */
    friend constexpr IntBitSet operator&(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & b.m_val); }
    /** Return an object with the binary OR between respective bits from a and b. */
    friend constexpr IntBitSet operator|(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val | b.m_val); }
    /** Return an object with the binary AND NOT between respective bits from a and b. */
    friend constexpr IntBitSet operator-(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & ~b.m_val); }
    /** Return an object with the binary XOR between respective bits from a and b. */
    friend constexpr IntBitSet operator^(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val ^ b.m_val); }
    /** Check if bitset a and bitset b are identical. */
    friend constexpr bool operator==(const IntBitSet& a, const IntBitSet& b) noexcept = default;
    /** Check if bitset a is a superset of bitset b (= every 1 bit in b is also in a). */
    constexpr bool IsSupersetOf(const IntBitSet& a) const noexcept { return (a.m_val & ~m_val) == 0; }
    /** Check if bitset a is a subset of bitset b (= every 1 bit in a is also in b). */
    constexpr bool IsSubsetOf(const IntBitSet& a) const noexcept { return (m_val & ~a.m_val) == 0; }
    /** Swap two bitsets. */
    friend constexpr void swap(IntBitSet& a, IntBitSet& b) noexcept { std::swap(a.m_val, b.m_val); }
};

/** A bitset implementation backed by N integers of type I. */
template<typename I, unsigned N>
class MultiIntBitSet
{
    // Only binary, unsigned, integer, types allowed.
    static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
    // Cannot be empty.
    static_assert(N > 0);
    /** The number of bits per integer. */
    static constexpr unsigned LIMB_BITS = std::numeric_limits<I>::digits;
    /** Number of elements this set type supports. */
    static constexpr unsigned MAX_SIZE = LIMB_BITS * N;
    // No overflow allowed here.
    static_assert(MAX_SIZE / LIMB_BITS == N);
    /** Array whose member integers store the bits of the set. */
    std::array<I, N> m_val;
    /** Dummy type to return using end(). Only used for comparing with Iterator. */
    class IteratorEnd
    {
        friend class MultiIntBitSet;
        constexpr IteratorEnd() = default;
    public:
        constexpr IteratorEnd(const IteratorEnd&) = default;
    };
    /** Iterator type returned by begin(), which efficiently iterates all 1 positions. */
    class Iterator
    {
        friend class MultiIntBitSet;
        const std::array<I, N>* m_ptr; /**< Pointer to array to fetch bits from. */
        I m_val; /**< The remaining bits of (*m_ptr)[m_idx]. */
        unsigned m_pos; /**< The last reported position. */
        unsigned m_idx; /**< The index in *m_ptr currently being iterated over. */
        constexpr Iterator(const std::array<I, N>& ref) noexcept : m_ptr(&ref), m_idx(0)
        {
            do {
                m_val = (*m_ptr)[m_idx];
                if (m_val) {
                    m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
                    break;
                }
                ++m_idx;
            } while(m_idx < N);
        }

    public:
        /** Do not allow external code to construct an Iterator. */
        Iterator() = delete;
        // Copying is allowed.
        constexpr Iterator(const Iterator&) noexcept = default;
        constexpr Iterator& operator=(const Iterator&) noexcept = default;
        /** Test whether we are done (can only compare with IteratorEnd). */
        friend constexpr bool operator==(const Iterator& a, const IteratorEnd&) noexcept
        {
            return a.m_idx == N;
        }
        /** Progress to the next 1 bit (only if != IteratorEnd). */
        constexpr Iterator& operator++() noexcept
        {
            Assume(m_idx < N);
            m_val &= m_val - I{1U};
            if (m_val == 0) {
                while (true) {
                    ++m_idx;
                    if (m_idx == N) break;
                    m_val = (*m_ptr)[m_idx];
                    if (m_val) {
                        m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
                        break;
                    }
                }
            } else {
                m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
            }
            return *this;
        }
        /** Get the current bit position (only if != IteratorEnd). */
        constexpr unsigned operator*() const noexcept
        {
            Assume(m_idx < N);
            return m_pos;
        }
    };

public:
    /** Construct an all-zero bitset. */
    constexpr MultiIntBitSet() noexcept : m_val{} {}
    /** Copy construct a bitset. */
    constexpr MultiIntBitSet(const MultiIntBitSet&) noexcept = default;
    /** Copy assign a bitset. */
    constexpr MultiIntBitSet& operator=(const MultiIntBitSet&) noexcept = default;
    /** Set a bit to 1. */
    void constexpr Set(unsigned pos) noexcept
    {
        Assume(pos < MAX_SIZE);
        m_val[pos / LIMB_BITS] |= I{1U} << (pos % LIMB_BITS);
    }
    /** Set a bit to the specified value. */
    void constexpr Set(unsigned pos, bool val) noexcept
    {
        Assume(pos < MAX_SIZE);
        m_val[pos / LIMB_BITS] = (m_val[pos / LIMB_BITS] & ~I(I{1U} << (pos % LIMB_BITS))) |
                                 (I{val} << (pos % LIMB_BITS));
    }
    /** Construct a bitset from a list of values. */
    constexpr MultiIntBitSet(std::initializer_list<unsigned> ilist) noexcept : m_val{}
    {
        for (auto pos : ilist) Set(pos);
    }
    /** Set a bitset to a list of values. */
    constexpr MultiIntBitSet& operator=(std::initializer_list<unsigned> ilist) noexcept
    {
        m_val.fill(0);
        for (auto pos : ilist) Set(pos);
        return *this;
    }
    /** Set a bit to 0. */
    void constexpr Reset(unsigned pos) noexcept
    {
        Assume(pos < MAX_SIZE);
        m_val[pos / LIMB_BITS] &= ~I(I{1U} << (pos % LIMB_BITS));
    }
    /** Retrieve a bit at the given position. */
    bool constexpr operator[](unsigned pos) const noexcept
    {
        Assume(pos < MAX_SIZE);
        return (m_val[pos / LIMB_BITS] >> (pos % LIMB_BITS)) & 1U;
    }
    /** Construct a bitset with the singleton pos. */
    static constexpr MultiIntBitSet Singleton(unsigned pos) noexcept
    {
        Assume(pos < MAX_SIZE);
        MultiIntBitSet ret;
        ret.m_val[pos / LIMB_BITS] = I{1U} << (pos % LIMB_BITS);
        return ret;
    }
    /** Construct a bitset with bits 0..count-1 (inclusive) set to 1. */
    static constexpr MultiIntBitSet Fill(unsigned count) noexcept
    {
        Assume(count <= MAX_SIZE);
        MultiIntBitSet ret;
        if (count) {
            unsigned i = 0;
            while (count > LIMB_BITS) {
                ret.m_val[i++] = I(~I{0});
                count -= LIMB_BITS;
            }
            ret.m_val[i] = I(~I{0}) >> (LIMB_BITS - count);
        }
        return ret;
    }
    /** Return the number of bits that this object holds. */
    static constexpr unsigned Size() noexcept { return MAX_SIZE; }
    /** Compute the number of 1 bits in the bitset. */
    unsigned constexpr Count() const noexcept
    {
        unsigned ret{0};
        for (I v : m_val) ret += PopCount(v);
        return ret;
    }
    /** Check if all bits are 0. */
    bool constexpr None() const noexcept
    {
        for (auto v : m_val) {
            if (v != 0) return false;
        }
        return true;
    }
    /** Check if any bits are 1. */
    bool constexpr Any() const noexcept { return !None(); }
    /** Return an object that iterates over all 1 bits (++ and * only allowed when != end()). */
    Iterator constexpr begin() const noexcept { return Iterator(m_val); }
    /** Return a dummy object to compare Iterators with. */
    IteratorEnd constexpr end() const noexcept { return IteratorEnd(); }
    /** Find the first element (requires Any()). */
    unsigned constexpr First() const noexcept
    {
        unsigned p = 0;
        while (m_val[p] == 0) {
            ++p;
            Assume(p < N);
        }
        return std::countr_zero(m_val[p]) + p * LIMB_BITS;
    }
    /** Find the last element (requires Any()). */
    unsigned constexpr Last() const noexcept
    {
        unsigned p = N - 1;
        while (m_val[p] == 0) {
            Assume(p > 0);
            --p;
        }
        return std::bit_width(m_val[p]) - 1 + p * LIMB_BITS;
    }
    /** Set this object's bits to be the binary OR between respective bits from this and a. */
    constexpr MultiIntBitSet& operator|=(const MultiIntBitSet& a) noexcept
    {
        for (unsigned i = 0; i < N; ++i) {
            m_val[i] |= a.m_val[i];
        }
        return *this;
    }
    /** Set this object's bits to be the binary AND between respective bits from this and a. */
    constexpr MultiIntBitSet& operator&=(const MultiIntBitSet& a) noexcept
    {
        for (unsigned i = 0; i < N; ++i) {
            m_val[i] &= a.m_val[i];
        }
        return *this;
    }
    /** Set this object's bits to be the binary AND NOT between respective bits from this and a. */
    constexpr MultiIntBitSet& operator-=(const MultiIntBitSet& a) noexcept
    {
        for (unsigned i = 0; i < N; ++i) {
            m_val[i] &= ~a.m_val[i];
        }
        return *this;
    }
    /** Set this object's bits to be the binary XOR between respective bits from this and a. */
    constexpr MultiIntBitSet& operator^=(const MultiIntBitSet& a) noexcept
    {
        for (unsigned i = 0; i < N; ++i) {
            m_val[i] ^= a.m_val[i];
        }
        return *this;
    }
    /** Check whether the intersection between two sets is non-empty. */
    constexpr bool Overlaps(const MultiIntBitSet& a) const noexcept
    {
        for (unsigned i = 0; i < N; ++i) {
            if (m_val[i] & a.m_val[i]) return true;
        }
        return false;
    }
    /** Return an object with the binary AND between respective bits from a and b. */
    friend constexpr MultiIntBitSet operator&(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
    {
        MultiIntBitSet r;
        for (unsigned i = 0; i < N; ++i) {
            r.m_val[i] = a.m_val[i] & b.m_val[i];
        }
        return r;
    }
    /** Return an object with the binary OR between respective bits from a and b. */
    friend constexpr MultiIntBitSet operator|(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
    {
        MultiIntBitSet r;
        for (unsigned i = 0; i < N; ++i) {
            r.m_val[i] = a.m_val[i] | b.m_val[i];
        }
        return r;
    }
    /** Return an object with the binary AND NOT between respective bits from a and b. */
    friend constexpr MultiIntBitSet operator-(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
    {
        MultiIntBitSet r;
        for (unsigned i = 0; i < N; ++i) {
            r.m_val[i] = a.m_val[i] & ~b.m_val[i];
        }
        return r;
    }
    /** Return an object with the binary XOR between respective bits from a and b. */
    friend constexpr MultiIntBitSet operator^(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
    {
        MultiIntBitSet r;
        for (unsigned i = 0; i < N; ++i) {
            r.m_val[i] = a.m_val[i] ^ b.m_val[i];
        }
        return r;
    }
    /** Check if bitset a is a superset of bitset b (= every 1 bit in b is also in a). */
    constexpr bool IsSupersetOf(const MultiIntBitSet& a) const noexcept
    {
        for (unsigned i = 0; i < N; ++i) {
            if (a.m_val[i] & ~m_val[i]) return false;
        }
        return true;
    }
    /** Check if bitset a is a subset of bitset b (= every 1 bit in a is also in b). */
    constexpr bool IsSubsetOf(const MultiIntBitSet& a) const noexcept
    {
        for (unsigned i = 0; i < N; ++i) {
            if (m_val[i] & ~a.m_val[i]) return false;
        }
        return true;
    }
    /** Check if bitset a and bitset b are identical. */
    friend constexpr bool operator==(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept = default;
    /** Swap two bitsets. */
    friend constexpr void swap(MultiIntBitSet& a, MultiIntBitSet& b) noexcept { std::swap(a.m_val, b.m_val); }
};

} // namespace bitset_detail

// BitSet dispatches to IntBitSet or MultiIntBitSet as appropriate for the requested minimum number
// of bits. Use IntBitSet up to 32-bit, or up to 64-bit on 64-bit platforms; above that, use a
// MultiIntBitSet of size_t.
template<unsigned BITS>
using BitSet = std::conditional_t<(BITS <= 32), bitset_detail::IntBitSet<uint32_t>,
               std::conditional_t<(BITS <= std::numeric_limits<size_t>::digits), bitset_detail::IntBitSet<size_t>,
               bitset_detail::MultiIntBitSet<size_t, CeilDiv(BITS, size_t{std::numeric_limits<size_t>::digits})>>>;

#endif // BITCOIN_UTIL_BITSET_H

Coverage Report

Created: 2026-06-01 18:35

Line	Count	Source
1		// Copyright (c) The Bitcoin Core developers
2		// Distributed under the MIT software license, see the accompanying
3		// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5		#ifndef BITCOIN_UTIL_BITSET_H
6		#define BITCOIN_UTIL_BITSET_H
7
8		#include <util/check.h>
9		#include <util/overflow.h>
10
11		#include <array>
12		#include <bit>
13		#include <cstdint>
14		#include <limits>
15		#include <type_traits>
16
17		/* This file provides data types similar to std::bitset, but adds the following functionality:
18		*
19		* - Efficient iteration over all set bits (compatible with range-based for loops).
20		* - Efficient search for the first and last set bit (First() and Last()).
21		* - Efficient set subtraction: (a - b) implements "a and not b".
22		* - Efficient non-strict subset/superset testing: IsSubsetOf() and IsSupersetOf().
23		* - Efficient set overlap testing: a.Overlaps(b)
24		* - Efficient construction of set containing 0..N-1 (S::Fill).
25		* - Efficient construction of a single set (S::Singleton).
26		* - Construction from initializer lists.
27		*
28		* Other differences:
29		* - BitSet<N> is a bitset that supports at least N elements, but may support more (Size() reports
30		* the actual number). Because the actual number is unpredictable, there are no operations that
31		* affect all positions (like std::bitset's operator~, flip(), or all()).
32		* - Various other unimplemented features.
33		*/
34
35		namespace bitset_detail {
36
37		/** Count the number of bits set in an unsigned integer type. */
38		template<typename I>
39		unsigned inline constexpr PopCount(I v)
40	0	{
41	0	static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
42	0	constexpr auto BITS = std::numeric_limits<I>::digits;
43		// Algorithms from https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation.
44		// These seem to be faster than std::popcount when compiling for non-SSE4 on x86_64.
45		if constexpr (BITS <= 32) {
46		v -= (v >> 1) & 0x55555555;
47		v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
48		v = (v + (v >> 4)) & 0x0f0f0f0f;
49		if constexpr (BITS > 8) v += v >> 8;
50		if constexpr (BITS > 16) v += v >> 16;
51		return v & 0x3f;
52	0	} else {
53	0	static_assert(BITS <= 64);
54	0	v -= (v >> 1) & 0x5555555555555555;
55	0	v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333);
56	0	v = (v + (v >> 4)) & 0x0f0f0f0f0f0f0f0f;
57	0	return (v * uint64_t{0x0101010101010101}) >> 56;
58	0	}
59	0	}
60
61		/** A bitset implementation backed by a single integer of type I. */
62		template<typename I>
63		class IntBitSet
64		{
65		// Only binary, unsigned, integer, types allowed.
66		static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
67		/** The maximum number of bits this bitset supports. */
68		static constexpr unsigned MAX_SIZE = std::numeric_limits<I>::digits;
69		/** Integer whose bits represent this bitset. */
70		I m_val;
71		/** Internal constructor with a given integer as contents. */
72	0	IntBitSet(I val) noexcept : m_val{val} {}
73		/** Dummy type to return using end(). Only used for comparing with Iterator. */
74		class IteratorEnd
75		{
76		friend class IntBitSet;
77		constexpr IteratorEnd() = default;
78		public:
79		constexpr IteratorEnd(const IteratorEnd&) = default;
80		};
81		/** Iterator type returned by begin(), which efficiently iterates all 1 positions. */
82		class Iterator
83		{
84		friend class IntBitSet;
85		I m_val; /*< The original integer's remaining bits. /
86		unsigned m_pos; /** Last reported 1 position (if m_pos != 0). */
87	0	constexpr Iterator(I val) noexcept : m_val(val), m_pos(0)
88	0	{
89	0	if (m_val != 0) m_pos = std::countr_zero(m_val); Branch (89:17): [True: 0, False: 0]
90	0	}
91		public:
92		/** Do not allow external code to construct an Iterator. */
93		Iterator() = delete;
94		// Copying is allowed.
95		constexpr Iterator(const Iterator&) noexcept = default;
96		constexpr Iterator& operator=(const Iterator&) noexcept = default;
97		/** Test whether we are done (can only compare with IteratorEnd). */
98		constexpr friend bool operator==(const Iterator& a, const IteratorEnd&) noexcept
99	0	{
100	0	return a.m_val == 0;
101	0	}
102		/** Progress to the next 1 bit (only if != IteratorEnd). */
103		constexpr Iterator& operator++() noexcept
104	0	{
105	0	Assume(m_val != 0);
106	0	m_val &= m_val - I{1U};
107	0	if (m_val != 0) m_pos = std::countr_zero(m_val); Branch (107:17): [True: 0, False: 0]
108	0	return *this;
109	0	}
110		/** Get the current bit position (only if != IteratorEnd). */
111		constexpr unsigned operator*() const noexcept
112	0	{
113	0	Assume(m_val != 0);
114	0	return m_pos;
115	0	}
116		};
117
118		public:
119		/** Construct an all-zero bitset. */
120	0	constexpr IntBitSet() noexcept : m_val{0} {}
121		/** Copy construct a bitset. */
122		constexpr IntBitSet(const IntBitSet&) noexcept = default;
123		/** Construct from a list of values. */
124		constexpr IntBitSet(std::initializer_list<unsigned> ilist) noexcept : m_val(0)
125		{
126		for (auto pos : ilist) Set(pos);
127		}
128		/** Copy assign a bitset. */
129		constexpr IntBitSet& operator=(const IntBitSet&) noexcept = default;
130		/** Assign from a list of positions (which will be made true, all others false). */
131		constexpr IntBitSet& operator=(std::initializer_list<unsigned> ilist) noexcept
132		{
133		m_val = 0;
134		for (auto pos : ilist) Set(pos);
135		return *this;
136		}
137		/** Construct a bitset with the singleton i. */
138		static constexpr IntBitSet Singleton(unsigned i) noexcept
139	0	{
140	0	Assume(i < MAX_SIZE);
141	0	return IntBitSet(I(1U) << i);
142	0	}
143		/** Construct a bitset with bits 0..count-1 (inclusive) set to 1. */
144		static constexpr IntBitSet Fill(unsigned count) noexcept
145	0	{
146	0	IntBitSet ret;
147	0	Assume(count <= MAX_SIZE);
148	0	if (count) ret.m_val = I(~I{0}) >> (MAX_SIZE - count); Branch (148:13): [True: 0, False: 0]
149	0	return ret;
150	0	}
151		/** Set a bit to 1. */
152		constexpr void Set(unsigned pos) noexcept
153	0	{
154	0	Assume(pos < MAX_SIZE);
155	0	m_val \|= I{1U} << pos;
156	0	}
157		/** Set a bit to the specified value. */
158		constexpr void Set(unsigned pos, bool val) noexcept
159		{
160		Assume(pos < MAX_SIZE);
161		m_val = (m_val & ~I(I{1U} << pos)) \| (I(val) << pos);
162		}
163		/** Set a bit to 0. */
164		constexpr void Reset(unsigned pos) noexcept
165	0	{
166	0	Assume(pos < MAX_SIZE);
167	0	m_val &= ~I(I{1U} << pos);
168	0	}
169		/** Retrieve a bit at the given position. */
170		constexpr bool operator[](unsigned pos) const noexcept
171	0	{
172	0	Assume(pos < MAX_SIZE);
173	0	return (m_val >> pos) & 1U;
174	0	}
175		/** Compute the number of 1 bits in the bitset. */
176	0	constexpr unsigned Count() const noexcept { return PopCount(m_val); }
177		/** Return the number of bits that this object holds. */
178	0	static constexpr unsigned Size() noexcept { return MAX_SIZE; }
179		/** Check if all bits are 0. */
180	0	constexpr bool None() const noexcept { return m_val == 0; }
181		/** Check if any bits are 1. */
182	0	constexpr bool Any() const noexcept { return !None(); }
183		/** Return an object that iterates over all 1 bits (++ and * only allowed when != end()). */
184	0	constexpr Iterator begin() const noexcept { return Iterator(m_val); }
185		/** Return a dummy object to compare Iterators with. */
186	0	constexpr IteratorEnd end() const noexcept { return IteratorEnd(); }
187		/** Find the first element (requires Any()). */
188		constexpr unsigned First() const noexcept
189	0	{
190	0	Assume(m_val != 0);
191	0	return std::countr_zero(m_val);
192	0	}
193		/** Find the last element (requires Any()). */
194		constexpr unsigned Last() const noexcept
195		{
196		Assume(m_val != 0);
197		return std::bit_width(m_val) - 1;
198		}
199		/** Set this object's bits to be the binary AND between respective bits from this and a. */
200	0	constexpr IntBitSet& operator\|=(const IntBitSet& a) noexcept { m_val \|= a.m_val; return *this; }
201		/** Set this object's bits to be the binary OR between respective bits from this and a. */
202	0	constexpr IntBitSet& operator&=(const IntBitSet& a) noexcept { m_val &= a.m_val; return *this; }
203		/** Set this object's bits to be the binary AND NOT between respective bits from this and a. */
204	0	constexpr IntBitSet& operator-=(const IntBitSet& a) noexcept { m_val &= ~a.m_val; return *this; }
205		/** Set this object's bits to be the binary XOR between respective bits from this as a. */
206		constexpr IntBitSet& operator^=(const IntBitSet& a) noexcept { m_val ^= a.m_val; return *this; }
207		/** Check if the intersection between two sets is non-empty. */
208	0	constexpr bool Overlaps(const IntBitSet& a) const noexcept { return m_val & a.m_val; }
209		/** Return an object with the binary AND between respective bits from a and b. */
210	0	friend constexpr IntBitSet operator&(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & b.m_val); }
211		/** Return an object with the binary OR between respective bits from a and b. */
212		friend constexpr IntBitSet operator\|(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val \| b.m_val); }
213		/** Return an object with the binary AND NOT between respective bits from a and b. */
214	0	friend constexpr IntBitSet operator-(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & ~b.m_val); }
215		/** Return an object with the binary XOR between respective bits from a and b. */
216		friend constexpr IntBitSet operator^(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val ^ b.m_val); }
217		/** Check if bitset a and bitset b are identical. */
218	0	friend constexpr bool operator==(const IntBitSet& a, const IntBitSet& b) noexcept = default;
219		/** Check if bitset a is a superset of bitset b (= every 1 bit in b is also in a). */
220	0	constexpr bool IsSupersetOf(const IntBitSet& a) const noexcept { return (a.m_val & ~m_val) == 0; }
221		/** Check if bitset a is a subset of bitset b (= every 1 bit in a is also in b). */
222	0	constexpr bool IsSubsetOf(const IntBitSet& a) const noexcept { return (m_val & ~a.m_val) == 0; }
223		/** Swap two bitsets. */
224		friend constexpr void swap(IntBitSet& a, IntBitSet& b) noexcept { std::swap(a.m_val, b.m_val); }
225		};
226
227		/** A bitset implementation backed by N integers of type I. */
228		template<typename I, unsigned N>
229		class MultiIntBitSet
230		{
231		// Only binary, unsigned, integer, types allowed.
232		static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
233		// Cannot be empty.
234		static_assert(N > 0);
235		/** The number of bits per integer. */
236		static constexpr unsigned LIMB_BITS = std::numeric_limits<I>::digits;
237		/** Number of elements this set type supports. */
238		static constexpr unsigned MAX_SIZE = LIMB_BITS * N;
239		// No overflow allowed here.
240		static_assert(MAX_SIZE / LIMB_BITS == N);
241		/** Array whose member integers store the bits of the set. */
242		std::array<I, N> m_val;
243		/** Dummy type to return using end(). Only used for comparing with Iterator. */
244		class IteratorEnd
245		{
246		friend class MultiIntBitSet;
247		constexpr IteratorEnd() = default;
248		public:
249		constexpr IteratorEnd(const IteratorEnd&) = default;
250		};
251		/** Iterator type returned by begin(), which efficiently iterates all 1 positions. */
252		class Iterator
253		{
254		friend class MultiIntBitSet;
255		const std::array<I, N>* m_ptr; /*< Pointer to array to fetch bits from. /
256		I m_val; /*< The remaining bits of (m_ptr)[m_idx]. */
257		unsigned m_pos; /*< The last reported position. /
258		unsigned m_idx; /*< The index in m_ptr currently being iterated over. */
259		constexpr Iterator(const std::array<I, N>& ref) noexcept : m_ptr(&ref), m_idx(0)
260		{
261		do {
262		m_val = (*m_ptr)[m_idx];
263		if (m_val) {
264		m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
265		break;
266		}
267		++m_idx;
268		} while(m_idx < N);
269		}
270
271		public:
272		/** Do not allow external code to construct an Iterator. */
273		Iterator() = delete;
274		// Copying is allowed.
275		constexpr Iterator(const Iterator&) noexcept = default;
276		constexpr Iterator& operator=(const Iterator&) noexcept = default;
277		/** Test whether we are done (can only compare with IteratorEnd). */
278		friend constexpr bool operator==(const Iterator& a, const IteratorEnd&) noexcept
279		{
280		return a.m_idx == N;
281		}
282		/** Progress to the next 1 bit (only if != IteratorEnd). */
283		constexpr Iterator& operator++() noexcept
284		{
285		Assume(m_idx < N);
286		m_val &= m_val - I{1U};
287		if (m_val == 0) {
288		while (true) {
289		++m_idx;
290		if (m_idx == N) break;
291		m_val = (*m_ptr)[m_idx];
292		if (m_val) {
293		m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
294		break;
295		}
296		}
297		} else {
298		m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
299		}
300		return *this;
301		}
302		/** Get the current bit position (only if != IteratorEnd). */
303		constexpr unsigned operator*() const noexcept
304		{
305		Assume(m_idx < N);
306		return m_pos;
307		}
308		};
309
310		public:
311		/** Construct an all-zero bitset. */
312		constexpr MultiIntBitSet() noexcept : m_val{} {}
313		/** Copy construct a bitset. */
314		constexpr MultiIntBitSet(const MultiIntBitSet&) noexcept = default;
315		/** Copy assign a bitset. */
316		constexpr MultiIntBitSet& operator=(const MultiIntBitSet&) noexcept = default;
317		/** Set a bit to 1. */
318		void constexpr Set(unsigned pos) noexcept
319		{
320		Assume(pos < MAX_SIZE);
321		m_val[pos / LIMB_BITS] \|= I{1U} << (pos % LIMB_BITS);
322		}
323		/** Set a bit to the specified value. */
324		void constexpr Set(unsigned pos, bool val) noexcept
325		{
326		Assume(pos < MAX_SIZE);
327		m_val[pos / LIMB_BITS] = (m_val[pos / LIMB_BITS] & ~I(I{1U} << (pos % LIMB_BITS))) \|
328		(I{val} << (pos % LIMB_BITS));
329		}
330		/** Construct a bitset from a list of values. */
331		constexpr MultiIntBitSet(std::initializer_list<unsigned> ilist) noexcept : m_val{}
332		{
333		for (auto pos : ilist) Set(pos);
334		}
335		/** Set a bitset to a list of values. */
336		constexpr MultiIntBitSet& operator=(std::initializer_list<unsigned> ilist) noexcept
337		{
338		m_val.fill(0);
339		for (auto pos : ilist) Set(pos);
340		return *this;
341		}
342		/** Set a bit to 0. */
343		void constexpr Reset(unsigned pos) noexcept
344		{
345		Assume(pos < MAX_SIZE);
346		m_val[pos / LIMB_BITS] &= ~I(I{1U} << (pos % LIMB_BITS));
347		}
348		/** Retrieve a bit at the given position. */
349		bool constexpr operator[](unsigned pos) const noexcept
350		{
351		Assume(pos < MAX_SIZE);
352		return (m_val[pos / LIMB_BITS] >> (pos % LIMB_BITS)) & 1U;
353		}
354		/** Construct a bitset with the singleton pos. */
355		static constexpr MultiIntBitSet Singleton(unsigned pos) noexcept
356		{
357		Assume(pos < MAX_SIZE);
358		MultiIntBitSet ret;
359		ret.m_val[pos / LIMB_BITS] = I{1U} << (pos % LIMB_BITS);
360		return ret;
361		}
362		/** Construct a bitset with bits 0..count-1 (inclusive) set to 1. */
363		static constexpr MultiIntBitSet Fill(unsigned count) noexcept
364		{
365		Assume(count <= MAX_SIZE);
366		MultiIntBitSet ret;
367		if (count) {
368		unsigned i = 0;
369		while (count > LIMB_BITS) {
370		ret.m_val[i++] = I(~I{0});
371		count -= LIMB_BITS;
372		}
373		ret.m_val[i] = I(~I{0}) >> (LIMB_BITS - count);
374		}
375		return ret;
376		}
377		/** Return the number of bits that this object holds. */
378		static constexpr unsigned Size() noexcept { return MAX_SIZE; }
379		/** Compute the number of 1 bits in the bitset. */
380		unsigned constexpr Count() const noexcept
381		{
382		unsigned ret{0};
383		for (I v : m_val) ret += PopCount(v);
384		return ret;
385		}
386		/** Check if all bits are 0. */
387		bool constexpr None() const noexcept
388		{
389		for (auto v : m_val) {
390		if (v != 0) return false;
391		}
392		return true;
393		}
394		/** Check if any bits are 1. */
395		bool constexpr Any() const noexcept { return !None(); }
396		/** Return an object that iterates over all 1 bits (++ and * only allowed when != end()). */
397		Iterator constexpr begin() const noexcept { return Iterator(m_val); }
398		/** Return a dummy object to compare Iterators with. */
399		IteratorEnd constexpr end() const noexcept { return IteratorEnd(); }
400		/** Find the first element (requires Any()). */
401		unsigned constexpr First() const noexcept
402		{
403		unsigned p = 0;
404		while (m_val[p] == 0) {
405		++p;
406		Assume(p < N);
407		}
408		return std::countr_zero(m_val[p]) + p * LIMB_BITS;
409		}
410		/** Find the last element (requires Any()). */
411		unsigned constexpr Last() const noexcept
412		{
413		unsigned p = N - 1;
414		while (m_val[p] == 0) {
415		Assume(p > 0);
416		--p;
417		}
418		return std::bit_width(m_val[p]) - 1 + p * LIMB_BITS;
419		}
420		/** Set this object's bits to be the binary OR between respective bits from this and a. */
421		constexpr MultiIntBitSet& operator\|=(const MultiIntBitSet& a) noexcept
422		{
423		for (unsigned i = 0; i < N; ++i) {
424		m_val[i] \|= a.m_val[i];
425		}
426		return *this;
427		}
428		/** Set this object's bits to be the binary AND between respective bits from this and a. */
429		constexpr MultiIntBitSet& operator&=(const MultiIntBitSet& a) noexcept
430		{
431		for (unsigned i = 0; i < N; ++i) {
432		m_val[i] &= a.m_val[i];
433		}
434		return *this;
435		}
436		/** Set this object's bits to be the binary AND NOT between respective bits from this and a. */
437		constexpr MultiIntBitSet& operator-=(const MultiIntBitSet& a) noexcept
438		{
439		for (unsigned i = 0; i < N; ++i) {
440		m_val[i] &= ~a.m_val[i];
441		}
442		return *this;
443		}
444		/** Set this object's bits to be the binary XOR between respective bits from this and a. */
445		constexpr MultiIntBitSet& operator^=(const MultiIntBitSet& a) noexcept
446		{
447		for (unsigned i = 0; i < N; ++i) {
448		m_val[i] ^= a.m_val[i];
449		}
450		return *this;
451		}
452		/** Check whether the intersection between two sets is non-empty. */
453		constexpr bool Overlaps(const MultiIntBitSet& a) const noexcept
454		{
455		for (unsigned i = 0; i < N; ++i) {
456		if (m_val[i] & a.m_val[i]) return true;
457		}
458		return false;
459		}
460		/** Return an object with the binary AND between respective bits from a and b. */
461		friend constexpr MultiIntBitSet operator&(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
462		{
463		MultiIntBitSet r;
464		for (unsigned i = 0; i < N; ++i) {
465		r.m_val[i] = a.m_val[i] & b.m_val[i];
466		}
467		return r;
468		}
469		/** Return an object with the binary OR between respective bits from a and b. */
470		friend constexpr MultiIntBitSet operator\|(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
471		{
472		MultiIntBitSet r;
473		for (unsigned i = 0; i < N; ++i) {
474		r.m_val[i] = a.m_val[i] \| b.m_val[i];
475		}
476		return r;
477		}
478		/** Return an object with the binary AND NOT between respective bits from a and b. */
479		friend constexpr MultiIntBitSet operator-(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
480		{
481		MultiIntBitSet r;
482		for (unsigned i = 0; i < N; ++i) {
483		r.m_val[i] = a.m_val[i] & ~b.m_val[i];
484		}
485		return r;
486		}
487		/** Return an object with the binary XOR between respective bits from a and b. */
488		friend constexpr MultiIntBitSet operator^(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
489		{
490		MultiIntBitSet r;
491		for (unsigned i = 0; i < N; ++i) {
492		r.m_val[i] = a.m_val[i] ^ b.m_val[i];
493		}
494		return r;
495		}
496		/** Check if bitset a is a superset of bitset b (= every 1 bit in b is also in a). */
497		constexpr bool IsSupersetOf(const MultiIntBitSet& a) const noexcept
498		{
499		for (unsigned i = 0; i < N; ++i) {
500		if (a.m_val[i] & ~m_val[i]) return false;
501		}
502		return true;
503		}
504		/** Check if bitset a is a subset of bitset b (= every 1 bit in a is also in b). */
505		constexpr bool IsSubsetOf(const MultiIntBitSet& a) const noexcept
506		{
507		for (unsigned i = 0; i < N; ++i) {
508		if (m_val[i] & ~a.m_val[i]) return false;
509		}
510		return true;
511		}
512		/** Check if bitset a and bitset b are identical. */
513		friend constexpr bool operator==(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept = default;
514		/** Swap two bitsets. */
515		friend constexpr void swap(MultiIntBitSet& a, MultiIntBitSet& b) noexcept { std::swap(a.m_val, b.m_val); }
516		};
517
518		} // namespace bitset_detail
519
520		// BitSet dispatches to IntBitSet or MultiIntBitSet as appropriate for the requested minimum number
521		// of bits. Use IntBitSet up to 32-bit, or up to 64-bit on 64-bit platforms; above that, use a
522		// MultiIntBitSet of size_t.
523		template<unsigned BITS>
524		using BitSet = std::conditional_t<(BITS <= 32), bitset_detail::IntBitSet<uint32_t>,
525		std::conditional_t<(BITS <= std::numeric_limits<size_t>::digits), bitset_detail::IntBitSet<size_t>,
526		bitset_detail::MultiIntBitSet<size_t, CeilDiv(BITS, size_t{std::numeric_limits<size_t>::digits})>>>;
527
528		#endif // BITCOIN_UTIL_BITSET_H