# Optimizing function that searches for binary patterns

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.

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