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

Tip

See here for more information on installing NuGet packages.

API Reference

Interfaces

Name	Description
IBitSet<TSelf>	Represents an ordered set of positive integers as a contiguous region of bits.

Structs

Name	Description
BitSet<T>	Represents an ordered set of positive integers as a contiguous region of bits using an unmanaged integer type.

Enumeration Structs

Name	Description
Subsets<T>, KSubsets<T>, Random<T>	Custom enumerable structs optimized for efficient BitSet<T> enumeration without additional allocation.

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.

Scenario	BitSet	HashSet	SortedSet
Construct 128 elements	113.6 ns, 0 B	1,060.3 ns, 6,000 B	3,457.4 ns, 5,168 B
Intersect 128 elements	166.7 ns, 0 B	2,983.3 ns, 0 B	18,100.0 ns, 3,416 B
Union 128 elements	66.7 ns, 0 B	2,900.0 ns, 40 B	19,366.7 ns, 200 B
Symmetric difference 128 elements	150.0 ns, 0 B	2,666.7 ns, 0 B	37,233.3 ns, 152 B

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

Scenario	LINQ Take	GetSubset
First 64 elements	245.5 ns, 136 B	43.1 ns, 0 B
Range 6..70	288.3 ns, 136 B	55.8 ns, 0 B
From-end range ^64..	499.4 ns, 224 B	126.7 ns, 0 B