1

我需要检查给定字节或一系列字节的特定位序列，如下所示：

  • 可以从零个或多个0s.
  • 可以从零个或多个1s.
  • 最后必须至少包含一个0。

换句话说，如果 bytes 的值不是0，那么我们只对包含连续1s后跟至少一个0结尾的值感兴趣。

我编写了以下代码来做到这一点，但想确保它高度优化。我觉得 if 分支中的多项检查可以优化，但不确定如何。请指教。

// The parameter [number] will NEVER be negative.
public static bool ConformsToPattern (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] == 1) // 00000001
                        || (bytes [b] == 3) // 00000011
                        || (bytes [b] == 7) // 00000111
                        || (bytes [b] == 15) // 00001111
                        || (bytes [b] == 31) // 00011111
                        || (bytes [b] == 63) // 00111111
                        || (bytes [b] == 127) // 01111111
                        || (bytes [b] == 255) // 11111111
                    )
                    {
                        // So far so good. Continue to the next byte with
                        // a possibility of more consecutive 1s.
                    }
                    else if
                    (
                        (bytes [b] == 128) // 10000000
                        || (bytes [b] == 192) // 11000000
                        || (bytes [b] == 224) // 11100000
                        || (bytes [b] == 240) // 11110000
                        || (bytes [b] == 248) // 11111000
                        || (bytes [b] == 252) // 11111100
                        || (bytes [b] == 254) // 11111110
                    )
                    {
                        moreOnesPossible = false;
                    }
                    else
                    {
                        return (false);
                    }
                }
                else
                {
                    if (bytes [b] > 0)
                    {
                        return (false);
                    }
                }
            }
        }
    }

    return (true);
}

重要提示：发送给函数的参数 [number]永远不会是负数，因此无需检查符号位。

4

6 回答 6

2

我要说的是，这些答案都没有解释

00000010
00000110
00001110
00011110
00111110
01111110    
00000100
00001100
00011100
00111100
01111100

等等等等等等。

这是我的字节数组方法：

public static bool ConformsToPattern(System.Numerics.BigInteger number)
{
    bool foundStart = false, foundEnd = false;
    int startPosition, stopPosition, increment;

    if (number.IsZero || number.IsPowerOfTwo)
        return true;
    if (!number.IsEven)            
        return false;
    byte[] bytes = number.ToByteArray();

    if(BitConverter.IsLittleEndian)
    {
        startPosition = 0;
        stopPosition = bytes.Length;
        increment = 1;
    }
    else
    {
        startPosition = bytes.Length - 1;
        stopPosition = -1;
        increment = -1;
    }

    for(int i = startPosition; i != stopPosition; i += increment)
    {
        byte n = bytes[i];      
        for(int shiftCount = 0; shiftCount < 8; shiftCount++)       
        {           
            if (!foundEnd)
            {
                if ((n & 1) == 1)
                    foundEnd = true;
                n = (byte)(n >> 1);
                continue;      
            }
            if (!foundStart)
            {
                if ((n & 1) == 0)   
                    foundStart = true;
                n = (byte)(n >> 1);
                continue;                
            }
            if (n == 0)
                continue;
            return false;
        }
    }
    if (foundEnd)
        return true;
    return false;
}

这是我的 BigInteger 方法：

public static bool ConformsToPattern(System.Numerics.BigInteger number)
{
    bool foundStart = false;
    bool foundEnd = false;
    if (number.IsZero || number.IsPowerOfTwo)
        return true;
    if (!number.IsEven)            
        return false;
    while (!number.IsZero)
    {
        if (!foundEnd)
        {
            if (!number.IsEven)
                foundEnd = true;
            number = number >> 1;
            continue;                
        }
        if (!foundStart)
        {
            if (number.IsEven)                
                foundStart = true;
            number = number >> 1;
            continue;                
        }
        return false;
    }
    if (foundEnd)
        return true;
    return false;
}

选择更适合您的。到目前为止，字节数组更快。BigIntegers 代码是 100% 准确的参考。

如果您不担心本机字节顺序，请删除该部分代码，但将其保留在其中将确保可移植到 x86 系统以外的其他系统。BigIntegers已经给了我IsZero,IsEven和IsPowerOfTwo，所以这不是额外的计算。我不确定这是否是最快的右移方法，因为有一个byte要转换的方法int，但是现在，我找不到另一种方法。至于使用bytevs shortvs intvs longfor 循环操作，如果您觉得它会更好地工作，则由您更改。我不确定您将发送什么样的 BigIntegers，所以我认为int会是安全的。您可以修改代码以删除for loop并复制粘贴代码 8 次，它可能会更快。或者您可以将其放入静态方法中。

于 2012-08-08T03:06:11.803 回答
1

这样的事情怎么样？如果你找到一个，那么之后唯一的事情可能是 1，直到找到一个 0。之后，只有 0s。这看起来会更快一点，因为它不会做不必要的或条件。

// The parameter [number] will NEVER be negative.
public static bool ConformsToPattern (System.Numerics.BigInteger number)
{
    byte [] bytes = null;
    bool moreOnesPossible = true;
    bool foundFirstOne = false;

    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(!foundFirstOne)
                    {
                        if
                        (
                            (bytes [b] == 1) // 00000001
                            || (bytes [b] == 3) // 00000011
                            || (bytes [b] == 7) // 00000111
                            || (bytes [b] == 15) // 00001111
                            || (bytes [b] == 31) // 00011111
                            || (bytes [b] == 63) // 00111111
                            || (bytes [b] == 127) // 01111111
                            || (bytes [b] == 255) // 11111111
                        )
                        {
                            foundFirstOne = true;
                            // So far so good. Continue to the next byte with
                            // a possibility of more consecutive 1s.
                        }
                        else if
                        (
                            (bytes [b] == 128) // 10000000
                            || (bytes [b] == 192) // 11000000
                            || (bytes [b] == 224) // 11100000
                            || (bytes [b] == 240) // 11110000
                            || (bytes [b] == 248) // 11111000
                            || (bytes [b] == 252) // 11111100
                            || (bytes [b] == 254) // 11111110
                        )
                        {
                            moreOnesPossible = false;
                        }
                        else
                        {
                            return (false);
                        }
                    }
                    else
                    {
                        if(bytes [b] != 255) // 11111111
                        {
                            if
                            (
                                (bytes [b] == 128) // 10000000
                                || (bytes [b] == 192) // 11000000
                                    || (bytes [b] == 224) // 11100000
                                || (bytes [b] == 240) // 11110000
                                || (bytes [b] == 248) // 11111000
                                || (bytes [b] == 252) // 11111100
                                || (bytes [b] == 254) // 11111110
                            )
                            {
                                moreOnesPossible = false;
                            }
                        }                            
                    }
                }
                else
                {
                    if (bytes [b] > 0)
                    {
                        return (false);
                    }
                }
            }
        }
    }

    return (true);
}
于 2012-08-07T13:34:37.600 回答
1

这是我自己写的方法。不是很优雅但很快。

/// <summary>
/// Checks to see if this cell lies on a major diagonal of a power of 2.
/// ^[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
    {
        return (true); // All bits are zero.
    }
    else
    {
        // The last bit should always be 0.
        if (number.IsEven)
        {
            bytes = number.ToByteArray();

            for (byte 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);
}
于 2012-08-08T19:40:29.587 回答
0

我是正则表达式的忠实粉丝，所以我想简单地将字节转换为字符串并针对正则表达式进行测试。但是，仔细定义模式很重要。通过阅读您的问题，我想出了这个问题：

^(?:1*)(?:0+)$

请检查一下：

    public static bool ConformsToPattern(System.Numerics.BigInteger number)
    {
        byte[] ByteArray = number.ToByteArray();

        Regex BinaryRegex = new Regex("^(?:1*)(?:0+)$", RegexOptions.Compiled);

        return ByteArray.Where<byte>(x => !BinaryRegex.IsMatch(Convert.ToString(x, 2))).Count() > 0;
    }
于 2012-08-07T13:06:13.310 回答
0

如果我理解正确，您必须只有 1 个连续的 1 系列，后跟连续的 0。

所以如果它必须以零结尾，它必须是偶数。中间的所有字节都必须全为 1，第一个和最后一个字节是您唯一的特殊情况。

         if (number.IsZero)
            return true;

         if (!number.IsEven)
            return false;


         var bytes = number.ToByteArray();

         for (int i = 0; i < bytes.Length; i++)
         {
            if (i == 0)  //first byte case
            {
               if (!(
                     (bytes[i] == 1) // 00000001 
                     || (bytes[i] == 3) // 00000011 
                     || (bytes[i] == 7) // 00000111 
                     || (bytes[i] == 15) // 00001111 
                     || (bytes[i] == 31) // 00011111 
                     || (bytes[i] == 63) // 00111111 
                     || (bytes[i] == 127) // 01111111 
                     || (bytes[i] == 255) // 11111111 
                    ))
               {
                  return false; 
               }
            }
            else if (i == bytes.Length) //last byte case
            {
               if (!(
                  (bytes[i] == 128) // 10000000 
                        || (bytes[i] == 192) // 11000000 
                        || (bytes[i] == 224) // 11100000 
                        || (bytes[i] == 240) // 11110000 
                        || (bytes[i] == 248) // 11111000 
                        || (bytes[i] == 252) // 11111100 
                        || (bytes[i] == 254) // 11111110 
                    ))
               {
                  return false;
               }
            }
            else //all bytes in the middle
            {
               if (bytes[i] != 255)
                  return false;
            }

         }
于 2012-08-07T13:34:18.927 回答
0

不确定这是否会比你已经拥有的更快或更慢，但这是可以尝试的（希望我没有搞砸逻辑）......

public bool ConformsToPattern(System.Numerics.BigInteger number) {
    bool moreOnesPossible = true;
    if (number == 0) {
        return true;
    }
    else {
        byte[] bytes = number.ToByteArray();
        if ((bytes[bytes.Length - 1] & 1) == 1) {
            return false;
        }
        else {
            for (byte b = 0; b < bytes.Length; b++) {
                if (moreOnesPossible) {
                    switch (bytes[b]) {
                        case 1:
                        case 3:
                        case 7:
                        case 15:
                        case 31:
                        case 63:
                        case 127:
                        case 255:
                            continue;
                        default:
                            switch (bytes[b]) {
                                case 128:
                                case 192:
                                case 224:
                                case 240:
                                case 248:
                                case 252:
                                case 254:
                                    moreOnesPossible = false;
                                    continue;
                                default:
                                    return false;
                            }
                    }
                }
                else {
                    if (bytes[b] > 0) { return (false); }
                }
            }
        }
    }
    return true;
}
于 2012-08-07T20:05:00.853 回答