For my faceted search Lucene.NET implementation I needed to get the cardinality of a BitArray. The cardinality is the number of bits in turned on. I found a VB snippet and I converted that one to C#.

Here is my implementation:

private static readonly byte[] _bitsSetArray256 = new byte[] { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 };

public static int GetCardinality( BitArray bitArray )
{
var array = (uint[]) bitArray.GetType().GetField( "m_array", System.Reflection.BindingFlags.NonPublic | System.Reflection.BindingFlags.Instance ).GetValue( bitArray );
int count = 0;

for ( int index = 0; index < array.Length; index ++ )
{
count += _bitsSetArray256[ array[ index ] & 0xFF ] + _bitsSetArray256[ ( array[ index ] >> 8 ) & 0xFF ] + _bitsSetArray256[ ( array[ index ] >> 16 ) & 0xFF ] + _bitsSetArray256[ ( array[ index ] >> 24 ) & 0xFF ];
}

return count;
}

The reflection access to the private field of BitArray isn’t exactly fast, but I will optimize it later and post the updated snippet right here.

I hope this implementation is as useful for you as it is for me.

For my work at Liones I has to implement a Lucene.NET search solution, including drill-down/faceted search. This was pretty hard to accomplish because there wasn’t much reference material, at least not for C#, but I just finished the first implementation and it works like a charm. I am not going to discus the implementation in detail because I decided to write some articles about it.

For now, I am thinking about the following articles:

1. Introduction to Lucene
2. Indexing basics
3. Search basics
4. Alternatives ( did you mean …)
5. Faceted search / Drill down
6. Class reference

Let met know if you have got more ideas for articles.