Skip to content

Instantly share code, notes, and snippets.

@nilpunch

nilpunch/BitSet.cs

Last active September 2, 2025 09:13
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save nilpunch/b217f56ffdb8182fee93f183be6ca0ef to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save nilpunch/b217f56ffdb8182fee93f183be6ca0ef to your computer and use it in GitHub Desktop.
Download ZIP
BitSet iteration
Raw
BitSet.cs
public class BitSet
{
public ulong[] Bits0 { get; private set; } = Array.Empty<ulong>();
public ulong[] Bits1 { get; private set; } = Array.Empty<ulong>();
public void Add(int id)
{
var id0 = id >> 6;
var id1 = id >> 12;
if (id0 >= Bits0.Length || id1 >= Bits1.Length)
{
var newBits0 = MathUtils.NextPowerOf2(id0 + 1);
var newBits1 = MathUtils.NextPowerOf2(id1 + 1);
if (newBits0 > Bits0.Length)
{
Bits0 = Bits0.Resize(newBits0);
}
if (newBits1 > Bits1.Length)
{
Bits1 = Bits1.Resize(newBits1);
}
}
var bit0 = 1UL << (id & 63);
var bit1 = 1UL << (id0 & 63);
if (Bits0[id0] == 0UL)
{
AddPage(id0);
Bits1[id1] |= bit1;
}
Bits0[id0] |= bit0;
}
public void Remove(int id)
{
var id0 = id >> 6;
var id1 = id >> 12;
if (id0 >= Bits0.Length)
{
return;
}
var bit0 = 1UL << (id & 63);
var bit1 = 1UL << (id0 & 63);
Bits0[id0] &= ~bit0;
if (Bits0[id0] == 0UL)
{
Bits1[id1] &= ~bit1;
RemovePage(id0);
}
}
public bool Has(int id)
{
var id0 = id >> 6;
if (id0 >= Bits0.Length)
{
return false;
}
var bit0 = 1UL << (id & 63);
return (Bits0[id0] & bit0) != 0UL;
}
protected virtual void AddPage(int page)
{
}
protected virtual void RemovePage(int page)
{
}
}
Raw
BitSetView.cs
public struct BitSetView<T1, T2, T3, T4>
{
public DataBitSet<T1> Bitset1 { get; }
public DataBitSet<T2> Bitset2 { get; }
public DataBitSet<T3> Bitset3 { get; }
public DataBitSet<T4> Bitset4 { get; }
public delegate void Iterator(ref T1 a, ref T2 b, ref T3 c, ref T4 d);
public BitSetView(DataBitSet<T1> bitset1, DataBitSet<T2> bitset2, DataBitSet<T3> bitset3, DataBitSet<T4> bitset4)
{
Bitset1 = bitset1;
Bitset2 = bitset2;
Bitset3 = bitset3;
Bitset4 = bitset4;
}
public void For(Iterator iterator)
{
var minBits1Length =
MathUtils.Min(Bitset1.Bits1.Length,
MathUtils.Min(Bitset2.Bits1.Length,
MathUtils.Min(Bitset3.Bits1.Length, Bitset4.Bits1.Length)));
for (var i = 0; i < minBits1Length; i++)
{
var bits1Result = Bitset1.Bits1[i] & Bitset2.Bits1[i] & Bitset3.Bits1[i] & Bitset4.Bits1[i];
var current0 = i << 6;
while (bits1Result != 0UL)
{
var skip1 = MathUtils.TZC(bits1Result);
bits1Result >>= skip1;
current0 += skip1;
if (bits1Result == 0UL)
{
break;
}
var iterate1 = MathUtils.TZC(~bits1Result);
if (bits1Result == ulong.MaxValue)
{
iterate1 = 64;
bits1Result = 0UL;
}
else
{
bits1Result >>= iterate1;
}
for (var j = 0; j < iterate1; j++, current0++)
{
var bits0Result = Bitset1.Bits0[current0] & Bitset2.Bits0[current0] & Bitset3.Bits0[current0] & Bitset4.Bits0[current0];
var dataOffset1 = Bitset1.Pages[current0].DataIndex & Bitset1.PageSizeMinusOne;
var dataOffset2 = Bitset2.Pages[current0].DataIndex & Bitset2.PageSizeMinusOne;
var dataOffset3 = Bitset3.Pages[current0].DataIndex & Bitset3.PageSizeMinusOne;
var dataOffset4 = Bitset4.Pages[current0].DataIndex & Bitset4.PageSizeMinusOne;
var dataPage1 = Bitset1.Data[Bitset1.Pages[current0].DataIndex >> Bitset1.PageSizePower];
var dataPage2 = Bitset2.Data[Bitset2.Pages[current0].DataIndex >> Bitset2.PageSizePower];
var dataPage3 = Bitset3.Data[Bitset3.Pages[current0].DataIndex >> Bitset3.PageSizePower];
var dataPage4 = Bitset4.Data[Bitset4.Pages[current0].DataIndex >> Bitset4.PageSizePower];
var current = 0;
while (bits0Result != 0UL)
{
var skip0 = MathUtils.TZC(bits0Result);
bits0Result >>= skip0;
current += skip0;
if (bits0Result == 0UL)
{
break;
}
var iterate0 = MathUtils.TZC(~bits0Result);
if (bits0Result == ulong.MaxValue)
{
iterate0 = 64;
bits0Result = 0UL;
}
else
{
bits0Result >>= iterate0;
}
for (var k = 0; k < iterate0; k++, current++)
{
iterator.Invoke(
ref dataPage1[dataOffset1 + current],
ref dataPage2[dataOffset2 + current],
ref dataPage3[dataOffset3 + current],
ref dataPage4[dataOffset4 + current]);
}
}
}
}
}
}
Raw
DataBitSet.cs
public class DataBitSet<T> : BitSet
{
public const int EndFreePage = -1;
public struct Page
{
public int DataIndex;
public int NextFreePage;
public Page(int dataIndex, int nextFreePage)
{
DataIndex = dataIndex;
NextFreePage = nextFreePage;
}
}
public T[][] Data { get; private set; } = Array.Empty<T[]>();
public Page[] Pages { get; private set; } = Array.Empty<Page>();
public int UsedPages { get; private set; }
public int NextFreePage { get; private set; } = EndFreePage;
public int PageSize { get; }
public int PageSizePower { get; }
public int PageSizeMinusOne { get; }
public DataBitSet(int pageSize = Constants.DefaultPageSize)
{
InvalidPageSizeException.ThrowIfNotPowerOf2<T>(pageSize);
PageSize = pageSize;
PageSizePower = MathUtils.FastLog2(pageSize);
PageSizeMinusOne = pageSize - 1;
}
public ref T Get(int id)
{
var pageOffset = Pages[id >> 6].DataIndex;
return ref Data[pageOffset >> PageSizePower][(pageOffset & PageSizeMinusOne) + (id & 63)];
}
protected override void AddPage(int page)
{
if (page >= Pages.Length)
{
Pages = Pages.Resize(MathUtils.NextPowerOf2(page + 1));
}
if (NextFreePage != EndFreePage)
{
var nextFreePage = NextFreePage;
NextFreePage = Pages[nextFreePage].NextFreePage;
Pages[page].DataIndex = Pages[nextFreePage].DataIndex;
}
else
{
var nextPageDataIndex = UsedPages << 6;
EnsurePageAt(nextPageDataIndex);
UsedPages++;
Pages[page].DataIndex = nextPageDataIndex;
}
}
protected override void RemovePage(int page)
{
Pages[page].NextFreePage = NextFreePage;
NextFreePage = page;
}
public void EnsurePageAt(int id)
{
EnsurePage(id >> PageSizePower);
}
public void EnsurePage(int page)
{
if (page >= Data.Length)
{
Data = Data.Resize(page + 1);
}
Data[page] ??= new T[PageSize];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment