BitSet 1.0.1

BitSet

A high-performance, memory-efficient ordered integer set implementation in C#. This library provides a compact representation of a set of ordered, positive integers using bit manipulation techniques, allowing for fast set operations such as union, intersection, and difference.

Table of Contents

• BitSet
  • Table of Contents
  • Features
  • Installation
  • API Reference
    • Interfaces
    • Structs
    • Enumeration Structs
  • Getting Started
  • Performance

Features

• Compact ordered integer sets backed by unmanaged binary integer types.
• Fast set operations through bitwise union, intersection, difference, symmetric difference, and complement.
• Allocation-free operations for small fixed-capacity sets such as BitSet<ulong> and BitSet<Int128>.
• Ordered helpers including First, Last, Rank, Select, PopFirst, and PopLast.
• ISet<int> compatibility for familiar collection APIs like Add, Remove, Contains, and SetEquals.
• Extension methods for efficient subset extraction, subset enumeration, and randomized iteration.

Installation

To install the NuGet package, run the following command:

dotnet add package BitSet

API Reference

Interfaces

Structs

Enumeration Structs

Getting Started

BitSet<T> stores set membership in the bits of an unmanaged integer type. For example, BitSet<ulong> can represent values from 0 through 63.

using BitSet;

BitSet<ulong> primes = [2, 3, 5, 7, 11, 13];

primes.Add(17);
primes.Remove(2);

Console.WriteLine(primes.Contains(11)); // True
Console.WriteLine(primes.Count);        // 6
Console.WriteLine(primes.First());      // 3
Console.WriteLine(primes.Last());       // 17

Set operations are implemented as bit operations, so common operations stay compact and allocation-free.

BitSet<ulong> evens = [0, 2, 4, 6, 8];
BitSet<ulong> odds = [1, 3, 5, 7, 9];
BitSet<ulong> small = [0, 1, 2, 3, 4];

BitSet<ulong> all = evens | odds;
BitSet<ulong> evenAndSmall = evens & small;
BitSet<ulong> oddOrSmallButNotBoth = odds ^ small;

BitSet<ulong> firstThree = all.GetSubset(3);
BitSet<ulong> middle = all.GetSubset(2..6);

Performance

The benchmarks in BitSet.Benchmarks compare BitSet<T> against HashSet<int> and SortedSet<int> for small ordered integer sets. These results were captured with BenchmarkDotNet on .NET 10 using an Intel Core Ultra 7 165U.

For subset extraction, the dedicated extension methods avoid the allocations required by LINQ-based alternatives.