C# port of the java.util.BitSet class

BitSet.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;

namespace BitSet {
    /* BitSet.cs -- A vector of bits.
     Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005  Free Software Foundation, Inc.

  This file is part of GNU Classpath.

  GNU Classpath is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2, or (at your option)
  any later version.

  GNU Classpath is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  aBlock with GNU Classpath; see the file COPYING.  If not, write to the
  Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  02110~0UL301 USA.

  Linking this library statically or dynamically with other modules is
  making a combined work based on this library.  Thus, the terms and
  conditions of the GNU General Public License cover the whole
  combination.

  As a special exception, the copyright holders of this library give you
  permission to link this library with independent modules to produce an
  executable, regardless of the license terms of these independent
  modules, and to copy and distribute the resulting executable under
  terms of your choice, provided that you also meet, for each linked
  independent module, the terms and conditions of the license of that
  module.  An independent module is a module which is not derived from
  or based on this library.  If you modify this library, you may extend
  this exception to your version of the library, but you are not
  obligated to do so.  If you do not wish to do so, delete this
  exception statement from your version. */

    /* Written using "Java Class Libraries", 2nd edition, ISBN 0-201-31002-3
     * hashCode algorithm taken from JDK 1.2 docs.
     */

    // Source ported to C# from: http://fuseyism.com/classpath/doc/java/util/BitSet-source.html

    namespace Util {
        using Block = UInt64;

        /// <summary>
        ///     This class can be thought of in two ways.  You can see it as a
        ///     vector of bits or as a set of non-negative integers.  The name
        ///     <code>BitSet</code> is a bit misleading.
        ///     It is implemented by a bit vector, but its equally possible to see
        ///     it as set of non-negative integer; each integer in the set is
        ///     represented by a set bit at the corresponding index.  The size of
        ///     this structure is determined by the highest integer in the set.
        ///     You can union, intersect and build (symmetric) remainders, by
        ///     invoking the logical operations and, or, andNot, resp. xor.
        ///     This implementation is NOT synchronized against concurrent access from
        ///     multiple threads. Specifically, if one thread is reading from a bitset
        ///     while another thread is simultaneously modifying it, the results are
        ///     undefined.
        ///     author Jochen Hoenicke
        ///     author Tom Tromey (tromey@cygnus.com)
        ///     author Eric Blake (ebb9@email.byu.edu)
        ///     status updated to 1.4
        /// </summary>
        [Serializable]
        public class BitSet : ICloneable, ISet<int>, IReadOnlyCollection<int>, ISet<uint> {
            // ReSharper disable once UnusedMember.Local
            private const long SerialVersionUid = 7997698588986878753L;

            /// <summary>
            ///     A common mask.
            /// </summary>
            private const int BlockMask = 0x3f;

            /// <summary>
            ///     The actual bits.
            ///     @serial the i'th bit is in bits[i/64] at position i%64 (where position
            ///     0 is the least significant).
            /// </summary>
            private ulong[] _bits;

            /// <summary>
            ///     Create a new empty bit set. All bits are initially false.
            /// </summary>
            public BitSet()
                : this(64) {
            }

            /// <summary>
            ///     Create a new empty bit set, with a given size.  This
            ///     constructor reserves enough space to represent the integers
            ///     from <code>0</code> to <code>nbits-1</code>.
            /// </summary>
            /// <param name="nbits">nbits the initial size of the bit set</param>
            public BitSet(int nbits) {
                if (nbits < 0)
                    throw new ArgumentOutOfRangeException(nameof(nbits), "nbits may not be negative");

                uint length = (uint) nbits >> 6;
                if ((nbits & BlockMask) != 0)
                    length++;
                _bits = new ulong[length];
            }

            private BitSet(ulong[] _bits, bool copy = true) {
                this._bits = copy ? (ulong[]) _bits.Clone() : _bits;
            }

            /// <summary>
            ///     Gets the logical number of bits actually used by this bit
            ///     set.  It returns the index of the highest set bit plus one.
            ///     Note that this method doesn't return the number of set bits.
            ///     Returns the index of the highest set bit plus one.
            /// </summary>
            public int Length {
                get {
                    // Set i to highest index that contains a non-zero value.
                    int i;
                    for (i = _bits.Length - 1; i >= 0 && _bits[i] == 0; --i) {
                    }

                    // if i < 0 all bits are cleared.
                    if (i < 0)
                        return 0;

                    // Now determine the exact length.
                    ulong b = _bits[i];
                    int len = (i + 1) * 64;
                    // b >= 0 checks if the highest bit is zero.
                    while (b >> ((sizeof(ulong) << 3) - 1) != 0UL) {
                        --len;
                        b <<= 1;
                    }

                    return len;
                }
            }

            /// <summary>
            ///     Returns the number of bits actually used by this bit set.  Note
            ///     that this method doesn't return the number of set bits, and that
            ///     future requests for larger bits will make this automatically grow.
            ///     Returns the number of bits currently used.
            /// </summary>
            public int Size => _bits.Length * 64;

            public bool this[int pos] {
                get => Get(pos);
                set => Set(pos, value);
            }

            /// <summary>
            ///     Create a clone of this bit set, that is an instance of the same
            ///     class and contains the same elements.  But it doesn't change when
            ///     this bit set changes.
            /// </summary>
            /// <returns>the clone of this object.</returns>
            object ICloneable.Clone() {
                return new BitSet(_bits);
            }

            public BitSet Clone() {
                return new BitSet(_bits);
            }

            /// <inheritdoc />
            void ICollection<int>.Add(int item) {
                Set(item);
            }

            /// <inheritdoc />
            public void ExceptWith(IEnumerable<int> other) {
                if (ReferenceEquals(this, other))
                    _bits = new ulong[1];
                else if (other is BitSet bvs)
                    AndNot(bvs);
                else {
                    foreach (int x in other)
                        Remove(x);
                }
            }

            /// <inheritdoc />
            public void IntersectWith(IEnumerable<int> other) {
                if (ReferenceEquals(this, other))
                    return;
                if (other is BitSet bvs)
                    And(bvs);
                else {
                    ISet<int> set;
                    if (other is ISet<int> ints)
                        set = ints;
                    else
                        set = new HashSet<int>(other);
                    var toremove = this.Where<int>(x => !set.Contains(x)).ToList();
                    foreach (int x in toremove)
                        Remove(x);
                }
            }

            /// <inheritdoc />
            public bool IsProperSubsetOf(IEnumerable<int> other) {
                if (ReferenceEquals(other, this))
                    return false;
                if (other is BitSet bvs)
                    return IsProperSubsetOf(bvs);

                var set = other is ISet<int> ts ? ts : new HashSet<int>(other);
                return set.Count > Count && this.All<int>(x => set.Contains(x));
                //TODO be more performant here
            }

            /// <inheritdoc />
            public bool IsProperSupersetOf(IEnumerable<int> other) {
                if (ReferenceEquals(other, this))
                    return false;
                if (other is BitSet bvs)
                    return IsProperSupersetOf(bvs);

                uint c = 0;
                foreach (int x in other) {
                    if (!Contains(x))
                        return false;
                    c++;
                }

                return _bits.ToSpan().PopCount() > c;
            }

            /// <inheritdoc />
            public bool IsSubsetOf(IEnumerable<int> other) {
                if (ReferenceEquals(other, this))
                    return true;
                if (other is BitSet bvs)
                    return IsSubsetOf(bvs);

                var set = other is ISet<int> ts ? ts : new HashSet<int>(other);
                //TODO be more performant here
                return this.All<int>(x => set.Contains(x));
            }

            /// <inheritdoc />
            public bool IsSupersetOf(IEnumerable<int> other) {
                if (ReferenceEquals(other, this))
                    return true;
                if (!(other is BitSet bvs))
                    return other.All(Contains);
                return IsSupersetOf(bvs);
            }

            /// <inheritdoc />
            public bool Overlaps(IEnumerable<int> other) {
                if (ReferenceEquals(other, this))
                    return true;
                if (!(other is BitSet bvs))
                    return other.Any(Contains);
                return Intersects(bvs);
            }

            /// <inheritdoc />
            public bool SetEquals(IEnumerable<int> other) {
                if (ReferenceEquals(this, other))
                    return true;

                return other switch
                {
                    BitSet bvs => SetEquals(bvs),
                    ISet<int> set => set.SetEquals(this),
                    _ => new HashSet<int>(this).SetEquals(other)
                };
            }

            /// <inheritdoc />
            public void SymmetricExceptWith(IEnumerable<int> other) {
                if (ReferenceEquals(this, other))
                    _bits = new ulong[1];
                else if (other is BitSet bvs) {
                    // symmetric except of two sets A and B is basically (A union B) except (A intersect B)
                    XOr(bvs);
                }
                else {
                    //TODO: be more efficient here...
                    ISet<int> set;
                    if (other is ISet<int> ts)
                        set = ts;
                    else
                        set = new HashSet<int>(other);
                    var intersection = new HashSet<int>();
                    foreach (int x in this)
                        if (set.Contains(x))
                            intersection.Add(x);
                    foreach (int x in intersection)
                        Remove(x);
                    foreach (int x in set)
                        if (!intersection.Contains(x))
                            Set(x);
                }
            }

            /// <inheritdoc />
            public void UnionWith(IEnumerable<int> other) {
                if (ReferenceEquals(this, other))
                    return;
                if (other is BitSet bvs)
                    Or(bvs);
                else {
                    foreach (int x in other)
                        Set(x);
                }
            }

            /// <inheritdoc />
            bool ISet<int>.Add(int item) {
                return Exchange(item, true);
            }

            /// <summary>
            ///     Sets all bits in the set to false.
            /// </summary>
            public void Clear() {
                Array.Fill(_bits, 0UL);
            }

            /// <inheritdoc />
            public bool Contains(int item) {
                return Get(item);
            }

            /// <inheritdoc />
            public void CopyTo(int[] array, int arrayIndex) {
                //TODO: be more efficient
                foreach (int x in this)
                    array[arrayIndex++] = x;
            }

            /// <inheritdoc />
            public bool Remove(int item) {
                return Exchange(item, false);
            }

            /// <inheritDoc />
            public int Count => Cardinality();

            /// <inheritDoc />
            public bool IsReadOnly => false;

            IEnumerator IEnumerable.GetEnumerator() {
                return GetEnumerator();
            }

            public IEnumerator<int> GetEnumerator() {
                for (int i = 0; i < _bits.Length; ++i) {
                    ulong bit = 1;
                    ulong word = _bits[i];
                    if (word == 0)
                        continue;
                    for (int j = 0; j < 64; ++j) {
                        if ((word & bit) != 0)
                            yield return 64 * i + j;

                        bit <<= 1;
                    }
                }
            }

            /// <inheritdoc />
            void ICollection<uint>.Add(uint item) {
                SetU(item);
            }

            /// <inheritdoc />
            public void ExceptWith(IEnumerable<uint> other) {
                if (ReferenceEquals(this, other))
                    _bits = new ulong[1];
                else if (other is BitSet bvs)
                    AndNot(bvs);
                else {
                    foreach (uint x in other)
                        Remove(x);
                }
            }

            /// <inheritdoc />
            public void IntersectWith(IEnumerable<uint> other) {
                if (ReferenceEquals(this, other))
                    return;
                if (other is BitSet bvs)
                    And(bvs);
                else {
                    ISet<uint> set;
                    if (other is ISet<uint> ints)
                        set = ints;
                    else
                        set = new HashSet<uint>(other);
                    var toremove = this.Where<uint>(x => !set.Contains(x)).ToList();
                    foreach (uint x in toremove)
                        Remove(x);
                }
            }

            /// <inheritdoc />
            public bool IsProperSubsetOf(IEnumerable<uint> other) {
                if (ReferenceEquals(other, this))
                    return false;
                if (other is BitSet bvs)
                    return IsProperSubsetOf(bvs);

                var set = other is ISet<uint> ts ? ts : new HashSet<uint>(other);
                return set.Count > Count && this.All<uint>(x => set.Contains(x));
                //TODO be more performant here
            }

            /// <inheritdoc />
            public bool IsProperSupersetOf(IEnumerable<uint> other) {
                if (ReferenceEquals(other, this))
                    return false;
                if (other is BitSet bvs)
                    return IsProperSupersetOf(bvs);

                uint c = 0;
                foreach (uint x in other) {
                    if (!Contains(x))
                        return false;
                    c++;
                }

                return _bits.ToSpan().PopCount() > c;
            }

            /// <inheritdoc />
            public bool IsSubsetOf(IEnumerable<uint> other) {
                if (ReferenceEquals(other, this))
                    return true;
                if (other is BitSet bvs)
                    return IsSubsetOf(bvs);

                var set = other is ISet<uint> ts ? ts : new HashSet<uint>(other);
                //TODO be more performant here
                return this.All<uint>(x => set.Contains(x));
            }

            /// <inheritdoc />
            public bool IsSupersetOf(IEnumerable<uint> other) {
                if (ReferenceEquals(other, this))
                    return true;
                if (!(other is BitSet bvs))
                    return other.All(Contains);
                return IsSupersetOf(bvs);
            }

            /// <inheritdoc />
            public bool Overlaps(IEnumerable<uint> other) {
                if (ReferenceEquals(other, this))
                    return true;
                if (!(other is BitSet bvs))
                    return other.Any(Contains);
                int len = Math.Min(_bits.Length, bvs._bits.Length);
                for (uint i = 0; i < len; ++i)
                    if ((_bits[i] & bvs._bits[i]) != 0)
                        return true;
                return false;
            }

            /// <inheritdoc />
            public bool SetEquals(IEnumerable<uint> other) {
                if (ReferenceEquals(this, other))
                    return true;

                return other switch
                {
                    BitSet bvs => SetEquals(bvs),
                    ISet<uint> set => set.SetEquals(this),
                    _ => new HashSet<uint>(this).SetEquals(other)
                };
            }

            /// <inheritdoc />
            public void SymmetricExceptWith(IEnumerable<uint> other) {
                if (ReferenceEquals(this, other))
                    _bits = new ulong[1];
                else if (other is BitSet bvs) {
                    // symmetric except of two sets A and B is basically (A union B) except (A intersect B)
                    XOr(bvs);
                }
                else {
                    //TODO: be more efficient here...
                    ISet<uint> set;
                    if (other is ISet<uint> ts)
                        set = ts;
                    else
                        set = new HashSet<uint>(other);
                    var intersection = new HashSet<uint>();
                    foreach (uint x in (IEnumerable<uint>) this)
                        if (set.Contains(x))
                            intersection.Add(x);
                    foreach (uint x in intersection)
                        Remove(x);
                    foreach (uint x in set)
                        if (!intersection.Contains(x))
                            SetU(x);
                }
            }

            /// <inheritdoc />
            public void UnionWith(IEnumerable<uint> other) {
                if (ReferenceEquals(this, other))
                    return;
                if (other is BitSet bvs)
                    Or(bvs);
                else {
                    foreach (uint x in other)
                        SetU(x);
                }
            }

            /// <inheritdoc />
            bool ISet<uint>.Add(uint item) {
                return ExchangeU(item, true);
            }

            /// <inheritdoc />
            public bool Contains(uint item) {
                return GetU(item);
            }

            /// <inheritdoc />
            public void CopyTo(uint[] array, int arrayIndex) {
                //TODO: be more efficient
                foreach (uint x in (IEnumerable<uint>) this)
                    array[arrayIndex++] = x;
            }

            /// <inheritdoc />
            public bool Remove(uint item) {
                return ExchangeU(item, false);
            }

            /// <inheritdoc />
            IEnumerator<uint> IEnumerable<uint>.GetEnumerator() {
                uint bitsLen = checked((uint) _bits.LongLength);
                for (uint i = 0; i < bitsLen; ++i) {
                    ulong bit = 1;
                    ulong word = _bits[i];
                    if (word == 0)
                        continue;
                    for (uint j = 0; j < 64; ++j) {
                        if ((word & bit) != 0)
                            yield return 64 * i + j;

                        bit <<= 1;
                    }
                }
            }

            public bool IsProperSupersetOf(BitSet bvs) {
                bool proper = _bits.Length != bvs._bits.Length;
                if (_bits.Length < bvs._bits.Length) {
                    if (bvs._bits.ToSpan(_bits.Length).PopCount() > 0)
                        return false;
                }

                int minlength = Math.Min(_bits.Length, bvs._bits.Length);
                for (uint i = 0; i < minlength; ++i)
                    if ((bvs._bits[i] & ~_bits[i]) != 0)
                        return false;
                    else if (bvs._bits[i] != _bits[i])
                        proper = true;
                return proper;
            }

            public bool IsSubsetOf(BitSet bvs) {
                if (_bits.Length > bvs._bits.Length) {
                    if (_bits.ToSpan(bvs._bits.Length).PopCount() > 0)
                        return false;
                }

                int minlength = Math.Min(_bits.Length, bvs._bits.Length);
                for (uint i = 0; i < minlength; ++i)
                    if ((_bits[i] & ~bvs._bits[i]) != 0)
                        return false;
                return true;
            }

            public bool IsSupersetOf(BitSet bvs) {
                if (_bits.Length < bvs._bits.Length) {
                    if (bvs._bits.ToSpan(_bits.Length).PopCount() > 0)
                        return false;
                }

                int minlength = Math.Min(_bits.Length, bvs._bits.Length);
                for (uint i = 0; i < minlength; ++i)
                    if ((bvs._bits[i] & ~_bits[i]) != 0)
                        return false;
                return true;
            }

            public bool SetEquals(BitSet bvs) {
                int len = Math.Min(_bits.Length, bvs._bits.Length);
                int maxLen = Math.Max(_bits.Length, bvs._bits.Length);
                for (uint i = 0; i < len; ++i)
                    if (_bits[i] != bvs._bits[i])
                        return false;
                if (maxLen == len)
                    return true;
                var larger = _bits.Length > len ? this : bvs;
                foreach (ulong x in larger._bits.ToSpan(len))
                    if (x != 0)
                        return false;

                return true;
            }

            public bool IsProperSubsetOf(BitSet bvs) {
                if (_bits.Length > bvs._bits.Length) {
                    if (_bits.ToSpan(bvs._bits.Length).PopCount() > 0)
                        return false;
                }

                bool proper = _bits.Length != bvs._bits.Length;
                int minlength = Math.Min(_bits.Length, bvs._bits.Length);
                for (uint i = 0; i < minlength; ++i)
                    if ((_bits[i] & ~bvs._bits[i]) != 0)
                        return false;
                    else if (_bits[i] != bvs._bits[i])
                        proper = true;
                return proper;
            }

            /// <summary>
            ///     Performs the logical AND operation on this bit set and the
            ///     given <code>set</code>.  This means it builds the intersection
            ///     of the two sets.  The result is stored into this bit set.
            /// </summary>
            /// <param name="bs">the second bit set</param>
            public void And(BitSet bs) {
                int max = Math.Min(_bits.Length, bs._bits.Length);
                int i;
                for (i = 0; i < max; ++i)
                    _bits[i] &= bs._bits[i];
                while (i < _bits.Length)
                    _bits[i++] = 0;
            }

            /// <summary>
            ///     Performs the logical AND operation on this bit set and the
            ///     complement of the given <code>bs</code>.  This means it
            ///     selects every element in the first set, that isn't in the
            ///     second set.  The result is stored into this bit set and is
            ///     effectively the set difference of the two.
            /// </summary>
            /// <param name="bs">the second bit set</param>
            public void AndNot(BitSet bs) {
                int i = Math.Min(_bits.Length, bs._bits.Length);
                while (--i >= 0)
                    _bits[i] &= ~bs._bits[i];
            }

            private int CardinalityFallback() {
                uint card = 0;
                for (int i = _bits.Length - 1; i >= 0; i--) {
                    ulong a = _bits[i];
                    // Take care of common cases.
                    if (a == 0)
                        continue;
                    if (a == ~0UL) {
                        card += 64;
                        continue;
                    }

                    // Successively collapse alternating bit groups into a sum.
                    a = ((a >> 1) & 0x5555555555555555L) + (a & 0x5555555555555555L);
                    a = ((a >> 2) & 0x3333333333333333L) + (a & 0x3333333333333333L);
                    uint b = (uint) ((a >> 32) + a);
                    b = ((b >> 4) & 0x0f0f0f0f) + (b & 0x0f0f0f0f);
                    b = ((b >> 8) & 0x00ff00ff) + (b & 0x00ff00ff);
                    card += ((b >> 16) & 0x0000ffff) + (b & 0x0000ffff);
                }

                return (int) card;
            }

            /// <summary>
            ///     Returns the number of bits set to true.
            /// </summary>
            public int Cardinality() {
                int ret = 0;
                for (int i = 0; i < _bits.Length; ++i)
                    ret += BitOperations.PopCount(_bits[i]);

                return ret;
            }

            public uint CardinalityU() {
                uint ret = 0;
                for (int i = 0; i < _bits.Length; ++i)
                    ret += _bits[i].PopCount();

                return ret;
            }

            public bool Exchange(int idx, bool nwVal) {
                int index = idx >> 6;
                ulong offset = 1ul << (idx & 63);
                bool ret = (_bits[index] & offset) != 0;
                if (nwVal != ret) {
                    if (nwVal)
                        _bits[index] |= offset;
                    else
                        _bits[index] &= ~offset;
                }

                return ret;
            }

            public bool ExchangeU(uint idx, bool nwVal) {
                uint index = idx >> 6;
                ulong offset = 1ul << (int) (idx & 63);
                bool ret = (_bits[index] & offset) != 0;
                if (nwVal != ret) {
                    if (nwVal)
                        _bits[index] |= offset;
                    else
                        _bits[index] &= ~offset;
                }

                return ret;
            }

            /// <summary>
            ///     Removes the integer <code>pos</code> from this set. That is
            ///     the corresponding bit is cleared.  If the index is not in the set,
            ///     this method does nothing.
            /// </summary>
            /// <param name="pos">a non-negative integer</param>
            public void Clear(int pos) {
                int offset = pos >> 6;
                Ensure(offset);
                _bits[offset] &= ~(1UL << pos);
            }

            /// <summary>
            ///     Sets the bits between from (inclusive) and to (exclusive) to false.
            /// </summary>
            /// <param name="from">the start range (inclusive)</param>
            /// <param name="to">the end range (exclusive)</param>
            public void Clear(int from, int to) {
                if (from < 0 || from > to)
                    throw new ArgumentOutOfRangeException();
                if (from == to)
                    return;
                uint loOffset = (uint) from >> 6;
                uint hiOffset = (uint) to >> 6;
                Ensure((int) hiOffset);
                if (loOffset == hiOffset) {
                    _bits[hiOffset] &= ((1UL << from) - 1) | (~0UL << to);
                    return;
                }

                _bits[loOffset] &= (1UL << from) - 1;
                _bits[hiOffset] &= ~0UL << to;
                for (int i = (int) loOffset + 1; i < hiOffset; i++)
                    _bits[i] = 0;
            }

            /// <summary>
            ///     Returns true if the <code>obj</code> is a bit set that contains
            ///     exactly the same elements as this bit set, otherwise false.
            /// </summary>
            /// <param name="obj">the object to compare to</param>
            /// <returns>true if obj equals this bit set</returns>
            public override bool Equals(object obj) {
                if (obj is null)
                    return false;
                if (!(obj.GetType() == typeof(BitSet)))
                    return false;
                var bs = (BitSet) obj;
                int max = Math.Min(_bits.Length, bs._bits.Length);
                int i;
                for (i = 0; i < max; ++i)
                    if (_bits[i] != bs._bits[i])
                        return false;
                // If one is larger, check to make sure all extra bits are 0.
                for (int j = i; j < _bits.Length; ++j)
                    if (_bits[j] != 0)
                        return false;
                for (int j = i; j < bs._bits.Length; ++j)
                    if (bs._bits[j] != 0)
                        return false;
                return true;
            }

            /// <summary>
            ///     Sets the bit at the index to the opposite value.
            /// </summary>
            /// <param name="index">the index of the bit</param>
            public void Flip(int index) {
                int offset = index >> 6;
                Ensure(offset);
                _bits[offset] ^= 1UL << index;
            }

            /// <summary>
            ///     Sets a range of bits to the opposite value.
            /// </summary>
            /// <param name="from">the low index (inclusive)</param>
            /// <param name="to">the high index (exclusive)</param>
            public void Flip(int from, int to) {
                if (from < 0 || from > to)
                    throw new ArgumentOutOfRangeException();
                if (from == to)
                    return;
                uint loOffset = (uint) from >> 6;
                uint hiOffset = (uint) to >> 6;
                Ensure((int) hiOffset);
                if (loOffset == hiOffset) {
                    _bits[hiOffset] ^= (~0UL << from) & ((1UL << to) - 1);
                    return;
                }

                _bits[loOffset] ^= ~0UL << from;
                _bits[hiOffset] ^= (1UL << to) - 1;
                for (int i = (int) loOffset + 1; i < hiOffset; i++)
                    _bits[i] ^= ~0UL;
            }

            /// <summary>
            ///     Returns true if the integer <code>bitIndex</code> is in this bit
            ///     set, otherwise false.
            /// </summary>
            /// <param name="pos">a non-negative integer</param>
            /// <returns>the value of the bit at the specified position</returns>
            public bool Get(int pos) {
                int offset = pos >> 6;
                if (offset >= _bits.Length)
                    return false;
                return (_bits[offset] & (1UL << pos)) != 0;
            }

            public bool GetU(uint pos) {
                uint index = pos >> 6;
                if (index > checked((uint) _bits.LongLength))
                    return false;
                ulong offset = 1ul << (int) (pos & 63);
                return (_bits[index] & offset) != 0;
            }


            /// <summary>
            ///     Returns a new <code>BitSet</code> composed of a range of bits from
            ///     this one.
            /// </summary>
            /// <param name="from">the low index (inclusive)</param>
            /// <param name="to">the high index (exclusive)</param>
            /// <returns></returns>
            public BitSet Get(int from, int to) {
                if (from < 0 || from > to)
                    throw new ArgumentOutOfRangeException();
                var bs = new BitSet(to - from);
                uint loOffset = (uint) from >> 6;
                if (loOffset >= _bits.Length || to == from)
                    return bs;

                int loBit = from & BlockMask;
                uint hiOffset = (uint) to >> 6;
                if (loBit == 0) {
                    uint len = Math.Min(hiOffset - loOffset + 1, (uint) _bits.Length - loOffset);
                    Array.Copy(_bits, loOffset, bs._bits, 0, len);
                    if (hiOffset < _bits.Length)
                        bs._bits[hiOffset - loOffset] &= (1UL << to) - 1;
                    return bs;
                }

                uint len2 = Math.Min(hiOffset, (uint) _bits.Length - 1);
                int reverse = 64 - loBit;
                int i;
                for (i = 0; loOffset < len2; loOffset++, i++)
                    bs._bits[i] = (_bits[loOffset] >> loBit) | (_bits[loOffset + 1] << reverse);
                if ((to & BlockMask) > loBit)
                    bs._bits[i++] = _bits[loOffset] >> loBit;
                if (hiOffset < _bits.Length)
                    bs._bits[i - 1] &= (1UL << (to - from)) - 1;
                return bs;
            }

            /// <summary>
            ///     Returns a hash code value for this bit set.  The hash code of
            ///     two bit sets containing the same integers is identical.  The algorithm
            ///     used to compute it is as follows:
            ///     Suppose the bits in the BitSet were to be stored in an array of
            ///     Block integers called <code>bits</code>, in such a manner that
            ///     bit <code>k</code> is set in the BitSet (for non-negative values
            ///     of <code>k</code>) if and only if
            ///     <code>((k/64) &lt; bits.length)
            /// && ((bits[k/64] & (1UL &lt;&lt; (bit % 64))) != 0)
            /// </code>
            ///     Then the following definition of the GetHashCode method
            ///     would be a correct implementation of the actual algorithm:
            ///     <pre>
            ///         public override int GetHashCode()
            ///         {
            ///         Block h = 1234;
            ///         for (int i = bits.length-1; i &gt;= 0; i--)
            ///         {
            ///         h ^= bits[i] * (i + 1);
            ///         }
            ///         return (int)((h >> 32) ^ h);
            ///         }
            ///     </pre>
            ///     Note that the hash code values changes, if the set is changed.
            /// </summary>
            /// <returns>the hash code value for this bit set.</returns>
            public override int GetHashCode() {
                ulong h = 1234;
                // ReSharper disable once NonReadonlyMemberInGetHashCode
                for (ulong i = (ulong) _bits.LongLength; i > 0;)
                    // ReSharper disable once NonReadonlyMemberInGetHashCode
                    h ^= i * _bits[--i];
                return (int) ((h >> 32) ^ h);
            }

            /// <summary>
            ///     Returns true if the specified BitSet and this one share at least one
            ///     common true bit.
            /// </summary>
            /// <param name="set">the set to check for intersection</param>
            /// <returns>true if the sets intersect</returns>
            public bool Intersects(BitSet set) {
                int i = Math.Min(_bits.Length, set._bits.Length);
                while (--i >= 0)
                    if ((_bits[i] & set._bits[i]) != 0)
                        return true;
                return false;
            }

            /// <summary>
            ///     Returns true if this set contains no true bits.
            /// </summary>
            /// <returns>true if all bits are false</returns>
            public bool IsEmpty() {
                for (int i = _bits.Length - 1; i >= 0; i--)
                    if (_bits[i] != 0)
                        return false;
                return true;
            }

            /// <summary>
            ///     Returns the index of the next false bit, from the specified bit
            ///     (inclusive).
            /// </summary>
            /// <param name="from">the start location</param>
            /// <returns>the first false bit</returns>
            public int NextClearBit(int from) {
                int offset = from >> 6;
                ulong mask = 1UL << from;
                while (offset < _bits.Length) {
                    ulong h = _bits[offset];
                    do {
                        if ((h & mask) == 0)
                            return from;
                        mask <<= 1;
                        from++;
                    } while (mask != 0);

                    mask = 1;
                    offset++;
                }

                return from;
            }

            /// <summary>
            ///     Returns the index of the next true bit, from the specified bit
            ///     (inclusive). If there is none, ~0UL is returned. You can iterate over
            ///     all true bits with this loop:
            ///     <pre>
            ///         for (int i = bs.nextSetBit(0); i &gt;= 0; i = bs.nextSetBit(i + 1))
            ///         {
            ///         // operate on i here
            ///         }
            ///     </pre>
            /// </summary>
            /// <param name="from">the start location</param>
            /// <returns>the first true bit, or ~0UL</returns>
            public int NextSetBit(int from) {
                int offset = from >> 6;
                ulong mask = 1UL << from;
                while (offset < _bits.Length) {
                    ulong h = _bits[offset];
                    do {
                        if ((h & mask) != 0)
                            return from;
                        mask <<= 1;
                        from++;
                    } while (mask != 0);

                    mask = 1;
                    offset++;
                }

                return -1;
            }

            /// <summary>
            ///     Performs the logical OR operation on this bit set and the
            ///     given <code>set</code>.  This means it builds the union
            ///     of the two sets.  The result is stored into this bit set, which
            ///     grows as necessary.
            /// </summary>
            /// <param name="bs">the second bit set</param>
            public void Or(BitSet bs) {
                Ensure(bs._bits.Length - 1);
                for (int i = bs._bits.Length - 1; i >= 0; i--)
                    _bits[i] |= bs._bits[i];
            }

            /// <summary>
            ///     Add the integer <code>bitIndex</code> to this set.  That is
            ///     the corresponding bit is set to true.  If the index was already in
            ///     the set, this method does nothing.  The size of this structure
            ///     is automatically increased as necessary.
            /// </summary>
            /// <param name="pos">a non-negative integer.</param>
            public void Set(int pos) {
                int offset = pos >> 6;
                Ensure(offset);
                _bits[offset] |= 1UL << pos;
            }

            public void SetU(uint pos) {
                uint offset = pos >> 6;
                Ensure(offset);
                _bits[offset] |= 1UL << (int) pos;
            }

            /// <summary>
            ///     Sets the bit at the given index to the specified value. The size of
            ///     this structure is automatically increased as necessary.
            /// </summary>
            /// <param name="index">the position to set</param>
            /// <param name="value">the value to set it to</param>
            public void Set(int index, bool value) {
                if (value)
                    Set(index);
                else
                    Clear(index);
            }

            /// <summary>
            ///     Sets the bits between from (inclusive) and to (exclusive) to true.
            /// </summary>
            /// <param name="from">the start range (inclusive)</param>
            /// <param name="to">the end range (exclusive)</param>
            public void Set(int from, int to) {
                if (from < 0 || from > to)
                    throw new ArgumentOutOfRangeException();
                if (from == to)
                    return;
                uint loOffset = (uint) from >> 6;
                uint hiOffset = (uint) to >> 6;
                Ensure((int) hiOffset);
                if (loOffset == hiOffset) {
                    _bits[hiOffset] |= (~0UL << from) & ((1UL << to) - 1);
                    return;
                }

                _bits[loOffset] |= ~0UL << from;
                _bits[hiOffset] |= (1UL << to) - 1;
                for (int i = (int) loOffset + 1; i < hiOffset; i++)
                    _bits[i] = ~0UL;
            }

            /// <summary>
            ///     Sets the bits between from (inclusive) and to (exclusive) to the
            ///     specified value.
            /// </summary>
            /// <param name="from">the start range (inclusive)</param>
            /// <param name="to">the end range (exclusive)</param>
            /// <param name="value">the value to set it to</param>
            public void Set(int from, int to, bool value) {
                if (value)
                    Set(from, to);
                else
                    Clear(from, to);
            }

            /// <summary>
            ///     Returns the string representation of this bit set.  This
            ///     consists of a comma separated list of the integers in this set
            ///     surrounded by curly braces.  There is a space after each comma.
            ///     A sample string is thus "{1, 3, 53}".
            /// </summary>
            /// <returns>the string representation.</returns>
            public override string ToString() {
                var r = new StringBuilder("{");
                bool first = true;
                for (int i = 0; i < _bits.Length; ++i) {
                    ulong bit = 1;
                    ulong word = _bits[i];
                    if (word == 0)
                        continue;
                    for (int j = 0; j < 64; ++j) {
                        if ((word & bit) != 0) {
                            if (!first)
                                r.Append(", ");
                            r.Append(64 * i + j);
                            first = false;
                        }

                        bit <<= 1;
                    }
                }

                return r.Append("}").ToString();
            }

            public void ForEach(Action<int> callBack) {
                for (int i = 0; i < _bits.Length; ++i) {
                    ulong bit = 1;
                    ulong word = _bits[i];
                    if (word == 0)
                        continue;
                    for (int j = 0; j < 64; ++j) {
                        if ((word & bit) != 0)
                            callBack(64 * i + j);

                        bit <<= 1;
                    }
                }
            }

            /// <summary>
            ///     Performs the logical XOR operation on this bit set and the
            ///     given <code>set</code>.  This means it builds the symmetric
            ///     remainder of the two sets (the elements that are in one set,
            ///     but not in the other).  The result is stored into this bit set,
            ///     which grows as necessary.
            /// </summary>
            /// <param name="bs">the second bit set</param>
            public void XOr(BitSet bs) {
                Ensure(bs._bits.Length - 1);
                for (int i = bs._bits.Length - 1; i >= 0; i--)
                    _bits[i] ^= bs._bits[i];
            }

            /// <summary>
            ///     Make sure the vector is big enough.
            /// </summary>
            /// <param name="lastElt">the size needed for the bits array</param>
            private void Ensure(int lastElt) {
                if (lastElt < _bits.Length)
                    return;
                var nd = new ulong[lastElt + 1];
                Array.Copy(_bits, 0, nd, 0, _bits.Length);
                _bits = nd;
            }

            private void Ensure(uint lastElt) {
                uint bitsLen = checked((uint) _bits.LongLength);
                if (lastElt < bitsLen)
                    return;
                var nd = new ulong[lastElt + 1];
                Array.Copy(_bits, 0, nd, 0, _bits.LongLength);
                _bits = nd;
            }

            // This is used by EnumSet for efficiency.
            public bool ContainsAll(BitSet other) {
                for (int i = other._bits.Length - 1; i >= 0; i--)
                    if ((_bits[i] & other._bits[i]) != other._bits[i])
                        return false;

                return true;
            }

            public static BitSet operator |(BitSet bvs1, BitSet bvs2) {
                var ret = bvs1.Clone();
                bvs1.Or(bvs2);
                return ret;
            }
            public static BitSet operator |(BitSet bvs1, IEnumerable<int> bvs2) {
                var ret = bvs1.Clone();
                bvs1.UnionWith(bvs2);
                return ret;
            }
            public static BitSet operator |(BitSet bvs1, IEnumerable<uint> bvs2) {
                var ret = bvs1.Clone();
                bvs1.UnionWith(bvs2);
                return ret;
            }
            public static BitSet operator +(BitSet bvs1, BitSet bvs2) {
                var ret = bvs1.Clone();
                bvs1.Or(bvs2);
                return ret;
            }
            public static BitSet operator +(BitSet bvs1, IEnumerable<int> bvs2) {
                var ret = bvs1.Clone();
                bvs1.UnionWith(bvs2);
                return ret;
            }
            public static BitSet operator +(BitSet bvs1, IEnumerable<uint> bvs2) {
                var ret = bvs1.Clone();
                bvs1.UnionWith(bvs2);
                return ret;
            }
            public static BitSet operator +(BitSet bvs1, int idx) {
                var ret = bvs1.Clone();
                bvs1.Set(idx);
                return ret;
            }
            public static BitSet operator +(BitSet bvs1, uint idx) {
                var ret = bvs1.Clone();
                bvs1.SetU(idx);
                return ret;
            }
            public static BitSet operator &(BitSet bvs1, BitSet bvs2) {
                var ret = bvs1.Clone();
                bvs1.And(bvs2);
                return ret;
            }
            public static BitSet operator &(BitSet bvs1, IEnumerable<int> bvs2) {
                var ret = bvs1.Clone();
                bvs1.IntersectWith(bvs2);
                return ret;
            }
            public static BitSet operator &(BitSet bvs1, IEnumerable<uint> bvs2) {
                var ret = bvs1.Clone();
                bvs1.IntersectWith(bvs2);
                return ret;
            }
            public static BitSet operator -(BitSet bvs1, BitSet bvs2) {
                var ret = bvs1.Clone();
                bvs1.AndNot(bvs2);
                return ret;
            }
            public static BitSet operator -(BitSet bvs1, IEnumerable<int> bvs2) {
                var ret = bvs1.Clone();
                bvs1.ExceptWith(bvs2);
                return ret;
            }
            public static BitSet operator -(BitSet bvs1, IEnumerable<uint> bvs2) {
                var ret = bvs1.Clone();
                bvs1.ExceptWith(bvs2);
                return ret;
            }
            public static BitSet operator ^(BitSet bvs1, BitSet bvs2) {
                var ret = bvs1.Clone();
                bvs1.XOr(bvs2);
                return ret;
            }
            public static BitSet operator ^(BitSet bvs1, IEnumerable<int> bvs2) {
                var ret = bvs1.Clone();
                bvs1.SymmetricExceptWith(bvs2);
                return ret;
            }
            public static BitSet operator ^(BitSet bvs1, IEnumerable<uint> bvs2) {
                var ret = bvs1.Clone();
                bvs1.SymmetricExceptWith(bvs2);
                return ret;
            }
            public static bool operator <(BitSet bvs1, BitSet bvs2) {
                return bvs1.IsProperSubsetOf(bvs2);
            }
            public static bool operator >(BitSet bvs1, BitSet bvs2) {
                return bvs1.IsProperSupersetOf(bvs2);
            }
            public static bool operator <(BitSet bvs1, IEnumerable<int> bvs2) {
                return bvs1.IsProperSubsetOf(bvs2);
            }
            public static bool operator >(BitSet bvs1, IEnumerable<int> bvs2) {
                return bvs1.IsProperSupersetOf(bvs2);
            }
            public static bool operator <(BitSet bvs1, IEnumerable<uint> bvs2) {
                return bvs1.IsProperSubsetOf(bvs2);
            }
            public static bool operator >(BitSet bvs1, IEnumerable<uint> bvs2) {
                return bvs1.IsProperSupersetOf(bvs2);
            }
            public static bool operator <=(BitSet bvs1, BitSet bvs2) {
                return bvs1.IsSubsetOf(bvs2);
            }
            public static bool operator >=(BitSet bvs1, BitSet bvs2) {
                return bvs1.IsSupersetOf(bvs2);
            }
            public static bool operator <=(BitSet bvs1, IEnumerable<int> bvs2) {
                return bvs1.IsSubsetOf(bvs2);
            }
            public static bool operator >=(BitSet bvs1, IEnumerable<int> bvs2) {
                return bvs1.IsSupersetOf(bvs2);
            }
            public static bool operator <=(BitSet bvs1, IEnumerable<uint> bvs2) {
                return bvs1.IsSubsetOf(bvs2);
            }
            public static bool operator >=(BitSet bvs1, IEnumerable<uint> bvs2) {
                return bvs1.IsSupersetOf(bvs2);
            }
        }
    }
}

BitSetHelper.cs

using System;
using System.Numerics;
using System.Runtime.Intrinsics.X86;

namespace BitSet
{
    using RTMethodImpl = System.Runtime.CompilerServices.MethodImplAttribute;
    using RTMethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
    public static class BitSetHelper
    {
        [RTMethodImpl(RTMethodImplOptions.AggressiveInlining)]
        public static uint PopCount(this ulong val) {
            unchecked {
                if (Popcnt.X64.IsSupported)
                    return (uint) Popcnt.X64.PopCount(val);
                return (uint) BitOperations.PopCount(val);
            }
        }
        public static uint PopCount(this Span<ulong> vec) {
            return PopCount((ReadOnlySpan<ulong>) vec);
        }
        public static uint PopCount(this ReadOnlySpan<ulong> vec) {
            uint ret = 0;
            foreach (var x in vec) {
                ret += PopCount(x);
            }
            return ret;
        }

        public static Span<T> ToSpan<T>(this T[] arr)
        {
            return new Span<T>(arr);
        }
        public static Span<T> ToSpan<T>(this T[] arr, int offs) {
            return new Span<T>(arr, offs, arr.Length - offs);
        }
    }
}