c# - 验证大整数的二进制模式 (BigInteger)

Question

我想测试一个正整数，看看它的二进制表示是否以零个或多个 1 开头，后跟一个或多个 0。

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

与正则表达式相同的表达方式是 ^[1]*[0]+$。当然这只是为了说明，我们不能使用正则表达式。

蛮力方法:

• 创建多个位掩码，并一起确定结果。
• 使用动态掩码遍历每个数字以确定结果。

问题是我正在处理可能有数十万位数字的巨大正整数，需要对数千个这样的数字执行此测试。

是否有更有效的方法来确定这种二进制模式？

更新

这是我尝试过的实现。尚未将时间与其他答案进行比较。

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

假设整数以二进制形式存储，分组到无符号整数数组 x[] 中，您可以这样做:

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;

在 y + (y & -y) 中，y & -y 返回 y 中设置的最低位。 (证明留给读者作为练习。)如果 y 中的所有高位都打开，添加最低位会导致进位传播通过所有这些位，将它们更改为零。如果这些较高位中的任何一个关闭，则进位停止，结果不为零。否则，结果为零。

你能改进上面的内容吗？假设比较和分支的成本高于 AND 等操作。在这种情况下，您可以使用二进制搜索来查找数组中值从全 1 变为全零或全不变为全零的位置。测试如上标识的关键字，然后将所有较高的值与在一起并测试所有值的结果，然后将所有较低的值一起或并测试所有零的结果。

这会为您提供二进制搜索，然后对每个单词进行一次加载和一次 AND 或 OR。很难对此进行改进。