逆向或算法？

Question

我先描述一下我的情况。

我有一个十六进制值列表，称为 BaseID。它们的选择使得任意数量的它们之间的逻辑“或”将为您提供一个唯一的ID，称为FinalID。也就是说，我的BaseID值如下。

BaseID = { 0x01, 0x02, 0x04, 0x08, 0x10, ... }

关键点是我不知道在运行程序之前我将拥有多少个 BaseID（我确实得到当我运行程序时，它是从文件中读取的 BaseID 列表），或者 BaseID 总数中有多少将用于创建最终ID。这是根据我的程序的其他部分决定的。例如，以下是我的程序中可能有的两个 FinalID。

FinalID = ( 0x01 | 0x04 ) = 0x05

FinalID = ( 0x02 | 0x04 | 0x10 ) = 0x16

现在，对任意数量的 BaseID 使用 OR 运算是很简单的部分。我的问题是，我需要从 FinalID 中提取用于创建 FinalID 的 BaseID。由于我选择了 BaseID，一旦使用 OR 运算，它们将始终为我提供唯一的 FinalID，因此我知道任何给定的 FinalID 都是使用一组特定的 BaseID 创建的。请注意，也可以仅使用一个 BaseID 创建 FinalID，这相当于 FinalID = ( BaseID | 0x00 )。

我知道我必须做什么来提取用于创建任何特定 FinalID 的 BaseID；我必须获取所涉及的 BaseID 的完整列表，然后在每个元素组合之间使用 OR 运算符来找出哪个组合是否给出了特定的 FinalID。

然而我发现很难将这种逻辑转换成程序。我正在使用 C# 和 .NET 3.5 Framework。任何建议/想法将非常感激。代码示例受到高度赞赏。

提前致谢！

Answer 1

好的，所以你已经有了一个位掩码...你需要做的就是将你的 FinalID 与每个可能的 BaseID 进行“AND” - 如果结果非零，则该 BaseID 会影响 FinalID：

// Or just go from 0... count and use 1 << x
foreach (int baseId in BaseIDs)
{
    if ((baseId & finalId) != 0)
    {
        ...
    }
}

我还建议你可以想要为此使用“flags”枚举，这将使您的语言集成方面的生活更简单。

Answer 2

这是我的建议：

        uint mask = 0x1;

        do
        {
            if ((finalId & mask) == mask)
            {
                // Base-ID found
            }
            mask <<= 1;
        }
        while (mask < finalId);

Answer 3

让我试试...

foreach(Id baseID in baseIDs)
{
    if(baseID & finalID != 0)
        results.Add(candidate);
}

应该不错。

Answer 4

如果您有所有 BaseID 的列表，那么与 FinalID 执行 AND 操作应该会告诉您它是否已被使用。

逻辑

Assume allBaseIds are sorted from lower to higher
For each (var baseId in allBaseIds)
{
   // FinalId will always be greater then consisting baseIds
   if(finalId < baseId)
     break;

   // As each base id represents a different bit, so its AND should result in baseId itself.
   if((finalId AND baseId) == baseId)
   {
      // This base id was used to make this final id.
   }
   else
   {
     // this base id was not used to make this final id
   }
}

Answer 5

var baseId = new int[] { 0x01, 0x02, 0x04, 0x08, 0x10 };
var finalId = 0x01|0x02|0x10;

foreach (var b in baseId)
{
    if ((finalId & b) == b)
    {
        Console.WriteLine(b);
    }
}

我将补充一点，使用 int 最多可以有 32 个 baseId，使用 long 最多可以有 64 个 baseId。理论上，使用 BigInteger 类您可以达到您想要的高度。