Optimizing function that searches for binary patterns

Question

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.

/// <summary>
/// A look up array of bit counts for the numbers 0 to 255 inclusive.
/// Declared static for performance.
/// </summary>
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,
};

/// <summary>
/// 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.
/// </summary>
public bool IsDiagonalMinorToPowerOfTwo ()
{
    int sum = 0;
    // this.X and this.Y are BigInteger types.
    byte [] bytes = (this.X + this.Y).ToByteArray();

    for (int i=0; i < bytes.Length; i++)
    {
        sum += BitCountLookupArray [bytes [i]];

        if (sum > 2)
        {
            return (false);
        }
    }

    return (true);
}

/// <summary>
/// Checks to see if this cell lies on a major diagonal of a power of 2.
/// The binary representation could contain any number of consecutive 1s
/// (could be none) and has to end with at least one 0.
/// ^[0]*[1]*[0]+$ denotes the regular expression of the binary pattern
/// we are looking for.
/// </summary>
public bool IsDiagonalMajorToPowerOfTwo ()
{
    byte [] bytes = null;

    bool moreOnesPossible = true;
    System.Numerics.BigInteger number = 0;

    number = System.Numerics.BigInteger.Abs(this.X - this.Y);

    if ((number == 0) || (number == 1))
    {
        // 00000000 && 00000001
        return (true);
    }
    else
    {
        // The last bit should always be 0.
        //if (number.IsEven)
        {
            bytes = number.ToByteArray();

            for (int b=0; b < bytes.Length; b++)
            {
                if (moreOnesPossible)
                {
                    switch (bytes [b])
                    {
                        case 001: // 00000001
                        case 003: // 00000011
                        case 007: // 00000111
                        case 015: // 00001111
                        case 031: // 00011111
                        case 063: // 00111111
                        case 127: // 01111111
                        case 255: // 11111111
                        {
                            // So far so good.
                            // Carry on testing subsequent bytes.

                            break;
                        }
                        case 128: // 10000000
                        case 064: // 01000000
                        case 032: // 00100000
                        case 016: // 00010000
                        case 008: // 00001000
                        case 004: // 00000100
                        case 002: // 00000010

                        case 192: // 11000000
                        case 096: // 01100000
                        case 048: // 00110000
                        case 024: // 00011000
                        case 012: // 00001100
                        case 006: // 00000110

                        case 224: // 11100000
                        case 112: // 01110000
                        case 056: // 00111000
                        case 028: // 00011100
                        case 014: // 00001110

                        case 240: // 11110000
                        case 120: // 01111000
                        case 060: // 00111100
                        case 030: // 00011110

                        case 248: // 11111000
                        case 124: // 01111100
                        case 062: // 00111110

                        case 252: // 11111100
                        case 126: // 01111110

                        case 254: // 11111110
                        {
                            moreOnesPossible = false;

                            break;
                        }

                        default:
                        {
                            return (false);
                        }
                    }
                }

                else
                {
                    if (bytes [b] > 0)
                    {
                        return (false);
                    }
                }
            }
        }
        //else
        {
            //return (false);
        }
    }

    return (true);
}

I've done all I can to optimize these functions and am now at a loss for ideas. By the way, I've also cached the byte [] for the BigInteger which is not reflected here.

NOTE: I'm not even sure if these binary patterns can be detected using some other more efficient algorithm. For those interested in context, I wrote these functions based on joriki's answer here.

Answer 1

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 << 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);
            }
        }
            ...

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);
            }
        }
        ...