3

我想测试一个正整数，看看它的二进制表示是否以零个或多个 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);
}
4

3 回答 3

3

假设整数以二进制形式存储，分组到一个无符号整数数组 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 变为全零或都不变为全零的位置。测试如上标识的关键字，然后将所有较高的值组合在一起并测试所有 1 的结果，然后将所有较低的值组合在一起并测试所有 0 的结果。

这为您提供了一个二分搜索，然后是一个加载和一个 AND 或 OR 用于每个单词。这将很难改进。

于 2012-08-05T18:01:40.800 回答
1

在最坏的情况下，如果没有存储有关输入的额外数据，您无法比 O( n ) 算法做得更好——其中n是位数——因为您需要检查数字中的每一位。

如果您在之前的操作过程中可以跟踪例如“最右边的 1”和“最左边的 0”，您可以通过检查它们是否确实是“10”来立即获得答案。

否则，您将不得不有效地遍历这些位以检查它是否正确。请注意，从左边开始遍历数字直到您击中 1，然后检查一切是否为 0（使用适当的极端情况）是 O( n )，而拥有 O( n ) 可能值的完整列表并检查它是否是等于（大概？）O（n）比较中的任何一个是O（n ^ 2），因此是个坏主意。

于 2012-08-05T16:05:08.197 回答
0

将您的二进制数据分成固定大小的块...... 32位...... 64位 - >将它们视为无符号整数

准备两个包含所有有效模式的哈希图，以及反向模式（以'0'开始，以'1'结束）......再次无符号整数

现在测试最左边的块是否包含在逆模式哈希图中...如果不是 -> 模式无效
现在测试最右边（非零）块是否包含在正常模式哈希图中...如果不是 ->模式无效

现在测试所有其他块是否等于所有位设置模式（应该是与无符号整数的比较）......如果所有都相等 -> 模式是有效的......否则......模式是无效的

于 2012-08-05T16:14:01.967 回答