Inside Bitcoin

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
310public:
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;