[RESOLVED] Bit-patterns.

Hello forum-members.

I'm currently in need of a (very) fast way of determining, if a 14 bit unsigned integer contains 5 consequtive set bits. Only the leftmost, if any, such pattern need be detected. I have ofc implemented the naive approach, but there may be a faster version that can be implemented.

Current code:

CSharp Code:

private ushort leftmost5bits(ushort v)
        {
            for (ushort p = 0x3e00; p >= 0x001f; p >>= 1) if ((p & v) == p) return p;
 
            return 0;
        }

For instance when counting set bits in a 14-bit number, I came across this excellent little algoritm, that does significantly better than the naive approach:

CSharp Code:

private byte countbits(ushort v)
        {
            return (byte)((v * 0x200040008001UL & 0x111111111111111UL) 'Modulus-operator' 0xf);
        }

EDIT: Above algorithm Sean Anderson + Bruce Dawson after original idea by Rich Schroeppel.
I'm hoping something similar can be found / coded for the pattern-matching problem above.

Thank you in advance for any input
Thomas

There is always a dumb brute force option of using a look up table. 14 bits would require 16384 entries. If you used bits the table could be reduced to 2kb.

c# Code:

if (MyLUT[number]) //using bools
//or
if (MyLUT[number >> 3] & (1<<(number & 7)) != 0) //using bits

Quote:

---

Originally Posted by Milk

There is always a dumb brute force option of using a look up table. 14 bits would require 16384 entries. If you used bits the table could be reduced to 2kb.

c# Code:

if (MyLUT[number]) //using bools
//or
if (MyLUT[number >> 3] & (1<<(number & 7)) != 0) //using bits

---

First off: thanks for your posting :)

I'm not entirely sure I understand that answer though (or my OP wasn't quite clear enough). I'm just looking for exactly 10 combinations of 5 consequtive bits in a 14-bit number. And while the loop only require 2 binary operations (shift + and) and 2 comparisions for each iteration, the sub containing the loop will be called so many times (millions), that cutting every superfluous operation will matter.
[In case I have the wrong idea about, what consequtive means (or I have misspelled it) - this is what I'm looking for: 0..0111110..0]

I gave the function at the bottom as an example of what I seek. A naive implementation of counting bits in a 14-bit number will require a loop iterating 14 times. But the displayed function [countbits] require only a single mul and a single & to perform exactly the same. Meaning ofc that it will execute several times faster. If a similar factor 10+ improvement can be found to the above problem (ie. 5-consequtive-bit patterns in 14 bit numbers), it will have a huge impact on the performance of my code.

It is for a piece of poker-analysing-software, in case someone wonders. Looking for 5 consequtive bits is ofc. the straights or straight-flushes, and counting bits is used on a binary | of 5 cards (disregarding suit) to determine if the hand is high card (5 bits), one pair (4 bits), 2 pairs (3 bits) or quads/fh (2 bits). The code will primarely be used to analyze omaha hands, each of which can be used with the community cards in 60 different combinations. Thus at a 10-player table, an analysis of a single hand will require comparisions of 600 5-card combinations. And for a given analysis to have statistical relevance, the code will have to go through several 100,000s of hands, meaning that each of the subs listed in my OP will get called 100M+ times each. This is why every single operation is costly.

Regards
Thomas


#EDIT: Just reread your post and understand it now. You are suggesting a lookup table of bools of every possible combination of 5 cards (no suit) to quickly determine if it's a straight. I never thought about that - 16,384 entries seems manageable and it will most certainly speed things up significantly. Thank you very much for your help :) [I disregarded the bit-solution fairly quickly - even if it uses up 8 times less memory, it will be significantly slower to execute. I will implement the first solution asap]

Have you come across the The Great Poker Hand Evaluator Roundup. It discusses a few cunning poker hand evaluation tricks.

Did you come across the bit counting algorithm at that stanford Bit Twiddling Hacks page? I love that page.

The following occurred to me on my way home, likely not as quick as an array look up but an improvement on what you had.

Code:

---

    public static int CountConsecutiveBits(int value)
        {
            int ct=0;
            while (value != 0)
            {
                ct++;
                value &= (value << 1);
            }
            return ct;
        }

---

it counts consecutive bits but it will only loop as many times as there are consecutive bits.

Quote:

---

Originally Posted by Milk

Have you come across the The Great Poker Hand Evaluator Roundup. It discusses a few cunning poker hand evaluation tricks.

Did you come across the bit counting algorithm at that stanford Bit Twiddling Hacks page? I love that page.

The following occurred to me on my way home, likely not as quick as an array look up but an improvement on what you had.

Code:

---

    public static int CountConsecutiveBits(int value)
        {
            int ct=0;
            while (value != 0)
            {
                ct++;
                value &= (value << 1);
            }
            return ct;
        }

---

it counts consecutive bits but it will only loop as many times as there are consecutive bits.

---

The bithacks was where I found the 14-bit set-bets counting function listed in the OP. It's an excellent page.
I haven't stumbled across the poker page before. Seems like an excellent resource and pretty much exactly something I can use, but sadly I don't have the time to browse it now. It will have to wait till tomorrow :)
Same is true with your function.
From a quick glance, it seems to follow the same principles as the Kernighan/Ritchie old ANSI C algorithm of counting set bits. I will try it out and check the results vs. a lookup table. Eventually though, I think the table is the way to go to get as much speed out of the code as possible.


Thanks again for all your help.
A fountain of information and great tips :thumb:

Regards Tom