Verifying binary patterns for large integers (BigInteger)

Question

I want to test a positive integer to see if its binary representation starts with zero or more 1's followed by one or more 0's.

00000000 // Valid
10000000 // Valid
11000000 // Valid
11100000 // Valid
11110000 // Valid
11111100 // Valid
11111110 // Valid
11111110 // Valid
11111111 // Not Valid
// Any other combination is Not Valid

The same expressed as a regular expression would be ^[1]*[0]+$. Of course this is only for clarification and we cannot use regex.

The brute force approaches:

• Create multiple bit masks, AND together to determine result.
• Loop through each digit with a dynamic mask to determine result.

The problem is that I am dealing with HUGE positive integers that can have hundreds of thousands of digits and need to perform this test for thousands of such numbers.

Is there a more efficient way to determine this binary pattern?

UPDATE

Here is the implementation I tried. Have not compared the time against other answers as yet.

public static bool IsDiagonalToPowerOfTwo (this System.Numerics.BigInteger number)
{
    byte [] bytes = null;
    bool moreOnesPossible = true;

    if (number == 0) // 00000000
    {
        return (true); // All bits are zero.
    }
    else
    {
        bytes = number.ToByteArray();

        if ((bytes [bytes.Length - 1] & 1) == 1)
        {
            return (false);
        }
        else
        {
            for (byte b=0; b < bytes.Length; b++)
            {
                if (moreOnesPossible)
                {
                    if (bytes [b] == 255)
                    {
                        // Continue.
                    }
                    else if
                    (
                        ((bytes [b] & 128) == 128) // 10000000
                        || ((bytes [b] & 192) == 192) // 11000000
                        || ((bytes [b] & 224) == 224) // 11100000
                        || ((bytes [b] & 240) == 240) // 11110000
                        || ((bytes [b] & 248) == 248) // 11111000
                        || ((bytes [b] & 252) == 252) // 11111100
                        || ((bytes [b] & 254) == 254) // 11111110
                    )
                    {
                        moreOnesPossible = false;
                    }
                    else
                    {
                        return (false);
                    }
                }
                else
                {
                    if (bytes [b] > 0)
                    {
                        return (false);
                    }
                }
            }
        }
    }

    return (true);
}

Answer 1

Supposing the integers are stored in binary, grouped into an array x[] of unsigned integers, you can do this:

Define UINT to be the unsigned integer type you are using for the grouped bits.
Define UMAX to be the maximum value of that type (all bits are on).

// Find first word that has a zero bit.
int i;
for (i = highest word in x; 0 <= i; --i)
    if (x[i] != UMAX)
        break;

// Return true if all bits in all of x[] are on.
if (i < 0)
    return true;

// Test whether word conforms to the ones-then-zeroes rule.
UINT y = x[i];
if (y + (y & -y))
    return false;

// Test whether all remaining words are zero.
for (; 0 <= i; --i)
    if (x[i])
        return false;

return true;

In y + (y & -y), y & -y returns the lowest bit set in y. (Proof left as an exercise for the reader.) If all higher bits in y are on, adding that lowest bit causes the carry to propagate through all those bits, changing them to zeroes. If any of those higher bits are off, the carry stops, and the result is not zero. Otherwise, the result is zero.

Can you improve on the above? Suppose comparison and branching have higher cost than operations like AND. In that case, you could use a binary search to find a location in the array where the values change from all ones to all zeroes or to neither. Test the critical word identified as above, then AND together all higher values and test the result of that for all ones, then OR together all lower values and test the result of that for all zeroes.

That gives you a binary search followed by one load and one AND or OR for each word. It would be hard to improve on that.