To your point, profile your data as you would your code. A sorted array of bit locations would represent a sparse bit set well enough to start, with O(N) stora

To your point, profile your data as you would your code. A sorted array of bit locations would represent a sparse bit set well enough to start, with O(N) storage and O(log N) access. Once the sets became large and/or dense, another data structure could be considered.