A Set of Cards

Many years ago I worked at a company that used a C library for evaluating poker hands. Never really understood how it worked; it used a lot of hard to read bit twiddling. A few years back I decided to see if I could come up with something similar in C#. I got something working but never did anything with it. I've now decided to dust off the code, update it to .NET 6.0 and take advantage of some new features on the way.

Many years ago I worked at a company that used a C library for evaluating poker hands. Never really understood how it worked; it used a lot of hard to read bit twiddling. A few years back I decided to see if I could come up with something similar in C#. I got something working but never did anything with it. I've now decided to dust off the code, update it to .NET 6.0 and take advantage of some new features on the way.

Representing Cards in Code

Playing cards have two attributes, rank (ace, five, queen, etc.) and suit. (Spades, clubs, etc.) They're simple to represent by enums in C#. I've chosen rank to start from zero rather than use the rank as the number for the enum, i.e. ace = 0, two = 1, rather than ace = 1, two = 2, etc. Whilst a little unusual it means I don't have to worry about checking for a value of zero all over the place, which is especially important as I'm going to make the Card object a readonly struct and using default(Card) would give a value of 0 for rank.

Bit Indices

Another way to represent a card is via bits. There are 52 cards in a deck and most CPUs these days are 64 bits. By using a bit to represent each card we can fit all the cards into a 64 bit long. It's simple to convert to this format. Multiply the suit value by 13 (as there are 13 ranks) and add the rank to give an index. This index is the position of the card in a full ordered deck of cards. Then left shift the value 1 by the index to get what I'm calling the bit index of the card.

To convert back we can take the bit index and work out the count of trailing zeros to get the index. .NET has the BitOperations.TrailingZeroCount method to get this for us. Most processors these days have a built in trailing zero count instruction making it nice and fast, but if they don't then that method has software fall backs. There are various ways to work out the trailing zero count; the excellent book Hacker's Delight covers several of them. Once we have the index we can get the suit with index % 13 and the rank with index / 13. However as I'm keeping a full deck cached in a static field I can just lookup into that instead.

Set Operations

Why bother with these bit indices? Well they make set operations easy. As each card is a single bit we can use a single long to represent a set of unique cards and we can use some bit twiddling for all the set operations we need in O(1). Some examples:

Working with a single card is no different from working with a set, so adding a card is just a union, removing is an except, etc.

The count of items in the set is just the number of set bits which can be obtained by the BitOperations.PopCount method. As for trailing zeros most modern processors have a dedicated instruction, but that method has software fallbacks if not. Again see Hacker's Delight for various methods.

Enumerating a Set

How do we enumerate over our set of cards? Again with bit twiddling. We can get the lowest bit in the set and convert it to a card for the current item in the enumeration. To move on to the next operation we can reset that bit. And then carry on until all bits have been reset. These two operations are simple enough; x & -x will extract the lowest set bit and x & (x - 1) will reset the lowest bit. However we can do slightly better as some processors have built in instructions for both of these (_blsi_u64 and _blsr_u64) which we can access via the .NET hardware intrinsics that were added with .NET Core 3.0. The System.Runtime.Intrinsics namespace gives methods to test if a given instruction is available on the CPU running your code and methods to call it if it is. The pattern is to check for availability, use the instruction if it's available or provide a fallback if not. The checks are treated as constants by the JIT meaning the check isn't performed at runtime but when the JIT compiles the code so there is no overhead of checking each time. Resetting the lowest set bit then becomes:

Bmi1.X64.IsSupported ? Bmi1.X64.ResetLowestSetBit(x) : x & (x - 1);

We can do a similar thing for extracting the lowest set bit.

The Source Code

You can find the source code for all of this at https://github.com/MrKWatkins/cards-cs.