反向OR算法

本文关键字：算法 OR 反向 | 更新日期: 2023-09-27 18:11:18

让我先描述一下我的情况。

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

BaseID＝｛0x01、0x02、0x04、0x08、0x10…｝

关键的一点是，我不知道在运行程序之前我会有多少个BaseID(当我从文件中读取程序时，我会在运行程序后得到一个BaseID列表(，或者不知道总共有多少BaseID将用于创建FinalID。它是根据我的程序的其他部分决定的。例如，下面是我的程序中可能有的两个FinalID。

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

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

现在，对任意数量的BaseID使用OR运算是很容易的部分。我的问题是，我需要从FinalID中提取用于创建FinalID的BaseID。由于我选择了BaseID，一旦使用OR运算，它们总是会给我一个唯一的FinalID，所以我知道任何给定的FinalID都是使用一组特定的BaseID创建的。请注意，FinalID也只能使用一个BaseID创建，该BaseID等效于FinalID=(BaseID|0x00(。

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

然而，我发现很难将这个逻辑转换成一个程序。我将C#与一起使用。NET 3.5框架。如有任何建议/想法，我们将不胜感激。非常感谢提供代码示例。

提前感谢！

反向OR算法

好吧，你有一个比特掩码。。。你所需要做的就是将你的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"枚举，这将使您的语言集成更加简单。

这是我的建议：

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

让我试试。。。

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

应该做得很好。

如果您有所有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
   }
}

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类，你可以达到你想要的高度。

相关文章：