patterncsharpMinor

Optimizing function that searches for binary patterns

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

codereview csharp stackoverflow c#performance .net

functionpatternsoptimizingforthatbinarysearches

Problem

I have the two functions that calculate whether or not a given coordinate (x, y) is a diagonal or anti-diagonal of another coordinate that is a power of 2. In other words if (x+/-k, y+/-k) == (cx, cy) where cx or cy is a power of 2, then the binary representation of (x+/-k, y+/-k) follows known patterns.

In case of minor diagonals, the binary representation of the product contains at most two 1s.

In case of major diagonals, the binary representation could contain any number of 1s (could be none) and has to end with at least one 0.

These functions are called on very large numbers that have around 5,000,000 bits and have become the most expensive call path. They end up taking 60% of the algorithm time and desperately need to be optimized.

Here are the functions.

```
///
/// A look up array of bit counts for the numbers 0 to 255 inclusive.
/// Declared static for performance.
///
public static readonly byte [] BitCountLookupArray = 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,
};

///
/// Checks to see if this cell lies on a minor diagonal of a power of 2.
/// The condition is met if the binary representation of the product contains
/// at most two 1s.
///
public bool IsD

Solution

The patterns I see are probably better produced by bit-shifting than by hard-coding:

...
        bytes = number.ToByteArray();
        foreach (byte b in bytes)
        {
            byte temp = 0;
            if (moreOnesPossible)
            {
                while(temp != 255 && moreOnesPossible)
                {
                   temp = (temp  0)
                    return (false);
            }
        }
            ...

For the absolute best performance speed, I'd recommend a Dictionary of all possible values and whether they are the pattern you're looking for or not. The Dictionary has to be hard-coded or generated as a one-time cost, but once it is you get constant access time making the whole thing not only linear-time and very fast, but rather elegant:

...
        bytes = number.ToByteArray();
        foreach (byte b in bytes)
        {
            if (moreOnesPossible)
            {
                if(!validPatterns[b])
                {
                    moreOnesPossible = false;
                    continue;
                }                       
            }
            else
            {
                if (b > 0)
                    return (false);
            }
        }
        ...

Code Snippets

...
        bytes = number.ToByteArray();
        foreach (byte b in bytes)
        {
            byte temp = 0;
            if (moreOnesPossible)
            {
                while(temp != 255 && moreOnesPossible)
                {
                   temp = (temp << 1) + 1;
                   if(b == temp)
                      continue;

                   byte shift = 0;
                   do{
                      if(bytes[b] == (temp << ++shift))
                      {
                          moreOnesPossible = false;
                          break;
                      }
                   } while(temp << shift < 128)
                }
            }
            else
            {
                if (bytes [b] > 0)
                    return (false);
            }
        }
            ...

...
        bytes = number.ToByteArray();
        foreach (byte b in bytes)
        {
            if (moreOnesPossible)
            {
                if(!validPatterns[b])
                {
                    moreOnesPossible = false;
                    continue;
                }                       
            }
            else
            {
                if (b > 0)
                    return (false);
            }
        }
        ...

Context

StackExchange Code Review Q#14817, answer score: 3

Revisions (0)

No revisions yet.