Programming Tips

Counting Rare Bits

When working with wheels, you will frequently need to count the numbers in an intersection of two sets, i.e. in how many numbers they match. Typically, that is a small number of numbers. So when sets are represented as bitmaps, only a few bits are set to 1, most are 0. Here is a fast way to count them in such case.

Take a 32-bit example (call it x):
00010000010010000010000000000000

Subtract 1, you get:
00010000010010000001111111111111

Then, "x and (x-1)" is:
00010000010010000000000000000000

You have cut down one bit.

So, the following loop will count them all:

Count := 0;
while x<>0 do begin
x := x and (x-1);
Inc(Count);
end;

Or, even when set bits are not rare, you might wish only to check if their number is not above some limit:

for i:=1 to limit do x := x and (x-1);
if x=0 then...

In any case, the spent time is only proportional to the number of bits to count, not to the size of the whole set.

Making Bits Rare

When testing a wheel, e.g. C(16,6,4,5), you need to match a "way", e.g. W={2,4,6,7,8}, to a "game", e.g. G={1,2,3,4,6,7}. When these are stored as bitmaps (e.g. in left-to-right order here), you would have:
0101011100000000 (W)
1111011000000000 (G)

The intersection, containing 4 numbers {2,4,6,7}, would have 4 bits to count:
0101011000000000 (W and G)

Instead, you can store the "game" as inverse, i.e. set each bit to 0 if the number is in and to 1 if it's not:
0101011100000000 (W)
0000100111111111 (not G)

The intersection now only contains number 8, which is in W but not in G, so there is only 1 (=5-4) bit to count:
0000000100000000 (W and not G)

In general with C(v,k,t,m), there is typically t > m-t for most practically useful wheels, so using this inversion will speed up the testing, when you count bits as suggested above ("Counting Rare Bits").

Combination Ordinal Numbers

Click here.